2

Strange Numbers

Difficulty: HARD
Contributed By
Vishal Modani
Avg. time to solve
45 min
Success Rate
55%

Problem Statement

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
``````

Sample Input 1 :

``````2
5
10
``````

Sample Output 1 :

``````0
3
``````

Explanation For Sample Input 1 :

``````Test case 1:
Numbers from 1 to 5 are 1, 2, 3, 4, 5.
1, when rotated 180 degrees, remains the same.
2, 3, 4, 5, when rotated 180 degrees, becomes invalid.
Therefore there are 0 strange numbers from 1 to 5.

Test case 2:
Strange numbers from 1 to 10 inclusive are 6, 9, and 10.
6, when rotated 180 degrees, becomes 9.
9, when rotated 180 degrees, becomes 6.
10, when rotated 180 degrees, becomes 01, which is the same as 1.
``````

Sample Input 2 :

``````1
16
``````

Sample Output 2:

``````4
``````

Explanation For Sample Input 2 :

``````Test case 1:
Strange numbers from 1 to 16 inclusive are 6, 9, 10, and 16.
6, when rotated 180 degrees, becomes 9.
9, when rotated 180 degrees, becomes 6.
10, when rotated 180 degrees, becomes 01, which is the same as 1.
16, when rotated 180 degrees, becomes 91.
``````
Console