# Strange Numbers

Posted: 23 Mar, 2021

Difficulty: Hard

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