Strange Numbers

Alice is very fond of digits. While she was playing with digits from 0 to 9, she noticed that when digits 0, 1, 6, 8, 9 are rotated 180 degrees, they become 0, 1, 9, 8, 6, respectively, and when digits 2, 3, 4, 5, and 7 are rotated 180 degrees, they become invalid.

After noticing such a property of digits, she started considering some numbers as strange numbers. According to her, a strange number is a number that, when rotated 180 degrees in a clockwise fashion, becomes a different number with each digit valid. As she is busy playing with digits, she gave you an integer ‘N’ and asked you to find the number of strange numbers from 1 to ‘N’ inclusive.

Note :

The rotated number can be greater(or smaller) than the original number.

Input Format :

The first line of the input contains an integer ‘T’ representing the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the integer given by Alice.

Output Format :

For each test case, print the number of strange numbers between 1 and ‘N’ inclusive.

The output of each test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
1 <= N <= 10 ^ 5

Time Limit: 1sec