Psyduck has short term memory loss problem and he forgot to propose his girlfriend Togepi on Valentines day. But now he has decided that he will propose her next week. As he was thinking about the way to propose her, he decides to buy a diamond ring for Togepi and for that he goes to Motu's shop to buy the ring. On his way back ,Chotu the villain appears and snatches the diamond ring .
After requesting multiple times , Chotu decides to return the ring if and only if Psyduck solves his question.

He gave Psyduck a number N and asked him to find the count of all non-negative numbers which are less than or equal to N , in which each pair of adjacent digits have atmost 1 absolute difference. For eg In number 12345 each pair of adjacent digits is having absolute difference of 1 where as in number 1235 last pair of adjacent digits have absolute difference of 2.
Now being a coder and IIITian, lets help him write a code that can solve his problem .

Input
First line contains T denoting number of test cases. Followed by T lines each containing an integer N.

Output
For each case print total count of such numbers.

Constraints
1<= T <= 100
1<= N <= 10⁹