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

The idea here is to perform a breadth-first search over all the numbers from 1 to ‘N’ inclusive with 0, 1, 6, 8, and 9 as their digits. Initially, we will insert all the numbers between 1 to ‘N’ inclusive having a single - digit with 0 or 1 or 6 or 8 or 9 as their digit into a queue. We will gradually increase the length(i.e., number of digits) of the numbers present in the queue and insert it into the queue if the number lies between 1 to ‘N’ inclusive. Refer to the below diagram for a clear understanding.

For all the numbers present in the queue, we will check if the current number is a strange number.

Algorithm:

- Declare an integer, say ‘cntStrange’ to count the total number of strange numbers in a given range, and initialize it with 0.
- Declare an integer, say ‘currNumber’, to keep track of the current number during our BFS traversal.
- Declare a queue of integers.
- Run a loop for ‘digit’ in [0, 1, 6, 8, 9]:
- If ‘digit’ lies between 1 and ‘N’ inclusive
- Insert ‘digit’ into the queue

- If ‘digit’ lies between 1 and ‘N’ inclusive
- Run a loop until the queue is not empty:
- Store the front of the queue in ‘currNumber’ and remove it from the queue.
- Call the ‘isStrangeNumber’ function to check if ‘currNumber’ is a strange number or not.
- If ‘currNumber’ is a strange number:
- Increment ‘cntStrange’ i.e., do cntStrange = cntStrange + 1.

- Append digits 0, 1, 6, 8, and 9 to ‘currNumber’
- Run a loop for ‘digit’ in [0, 1, 6, 8, 9]:
- Declare an integer, say ‘appendedNumber’
- Update ‘appendedNumber’ as ‘appendedNumber’ = currNumber * 10 + digit
- If ‘appendedNumber’ lies between 1 and ‘N’, inclusive
- Insert ‘appendedNumber’ into the queue.

- Return ‘cntStrange’.

Description of ‘isStrangeNumber’ function

This function is used to check whether the current number is a strange number or not.

This function will take one parameter:

- currNumber: An integer denoting the current number.

bool isStrangeNumber(currNumber):

- Declare a variable ‘rotatedNumber’ to store the value of ‘currNumber’ after rotating 180 degrees.
- Declare a variable ‘dummy’ and initialize it with ‘currNumber’.
- Run a loop while ‘dummy’ is greater than 0.
- Declare a variable ‘currDigit’ and initialize it with the rightmost digit of ‘dummy’, i.e., do currDigit = dummy % 10.
- Remove the rightmost digit of ‘dummy’, i.e., do dummy = dummy / 10
- If ‘currDigit’ is 6, then make it 9, or if the ‘currDigit is 9, make it 6, i.e., rotate the ‘currDigit’ by 180 degrees.
- Append the ‘currDigit’ to ‘rotatedNumber’ i.e. do rotatedNumber = rotatedNumber * 10 + currDigit.

- If ‘currNumber’ is not equal to ‘rotatedNumber’ then return true, as the current number follows properties of a strange number.
- Else return false, as the current number does not follow properties of a strange number as after rotating, the number must be different.

The idea here is to perform a depth-first search over all the numbers from 1 to ‘N’ inclusive with 0, 1, 6, 8, and 9 as their digits. Initially, we will start the depth-first search from all the numbers between 1 to ‘N’ inclusive having a single - digit with 0 or 1 or 6 or 8 or 9 as their first digit. We will gradually increase the length(i.e., number of digits) of the numbers and recursively do a depth-first search if the number lies between 1 to ‘N’ inclusive. For every number that we encounter during the depth-first search, we will check if it is a strange number or not. If it is a strange number, then we will increment our answer.

Algorithm:

- Declare an integer, say ‘cntStrange’ to count the total number of strange numbers in a given range.
- Call the ‘depthFirstSearch’ function with ‘N’ and 0 as arguments and store its returned value into ‘cntStrange’
- Return ‘cntStrange’

Description of ‘isStrangeNumber’ function

This function is used to check whether the current number is a strange number or not.

This function will take one parameter:

- currNumber: An integer denoting the current number.

bool isStrangeNumber(currNumber):

- Declare a variable ‘rotatedNumber’ to store the value of ‘currNumber’ after rotating 180 degrees.
- Declare a variable ‘dummy’ and initialize it with ‘currNumber’.
- Run a loop while ‘dummy’ is greater than 0.
- Declare a variable ‘currDigit’ and initialize it with the rightmost digit of ‘dummy’, i.e., do currDigit = dummy % 10.
- Remove the rightmost digit of ‘dummy’, i.e., do dummy = dummy / 10
- If ‘currDigit’ is 6, then make it 9, or if the ‘currDigit is 9, make it 6, i.e., rotate the ‘currDigit’ by 180 degrees.
- Append the ‘currDigit’ to ‘rotatedNumber’ i.e. do rotatedNumber = rotatedNumber * 10 + currDigit.

- If ‘currNumber’ is not equal to ‘rotatedNumber’ then return true, as the current number follows properties of a strange number.
- Else return false, as the current number does not follow properties of a strange number as after rotating, the number must be different.

Description of ‘depthFirstSearch’ function

This function will take two parameters:

- N: An integer given in the problem.
- currNumber: An integer denoting the current number in depth-first search.

int depthFirstSearch(N, currNumber):

- Declare a variable ‘answer’ to count the total number of strange numbers in a given range and initialize it with 0.
- Call the ‘isStrangeNumber’ function to check if ‘currNumber’ is a strange number or not.
- If ‘currNumber’ is a strange number:
- Increment ‘answer’ i.e., do answer = answer + 1.

- Append digits 0, 1, 6, 8, and 9 to ‘currNumber’
- Run a loop for ‘digit’ in [0, 1, 6, 8, 9]:
- Declare an integer, say ‘appendedNumber’
- Make appendedNumber = currNumber * 10 + digit
- If ‘appendedNumber’ lies between 1 and ‘N’, inclusive
- Declare an integer, say ‘currAnswer’
- Call the ‘depthFirstSearch’ function with ‘N’ and ‘appendedNumber’ as arguments and store its returned value into ‘currAnswer’
- Add ‘currAnswer’ to the ‘answer’ i.e. do answer = answer + currAnswer

- Return ‘answer’