The rotated number can be greater(or smaller) than the original number.
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.
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.
You do not need to print anything, it has already been taken care of. Just implement the given function.
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.
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: