# Special Numbers

#### A special number is defined as a number in which each digit of the number is between 0 to 5 (both inclusive) i.e. each digit belongs to the set S = {0, 1, 2, 3, 4, 5}.

#### Given a number N, your task is to find the Nth special number.

##### Input Format

```
The first line of input contains an integer T representing the number of test cases.
The first line of each test case contains one integer N denoting the number.
```

##### Output Format:

```
For each test case, on a separate line, output one integer - Nth special number.
```

##### Note :

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

##### Constraints:

```
1 <= T <= 1000
1 <= N <= 10^6
Where ‘T’ is the number of test cases, ‘N’ the given number.
Time limit: 1 sec
```

**Approach : **

The first six special numbers are 0, 1, 2, 3, 4 and 5. The next six special numbers are 10, 11, 12, 13, 14 and 15. The next six special numbers are 20, 21, 22, 23, 24, 25, and so on.

A pattern can be observed here for the chains of six-

Let’s say we have an **ans** array initially filled with numbers from 0 to 5, i.e the 1st six special numbers. The next chain of numbers in the series would be nothing but 10 * 1 + 0 = 10, 10 * 1 + 1, ……., 10 * 1 + 5. The next chain would be 10 * 2 + 0, 10 * 2 + 1, ………., 10 * 2 + 5.

Similarly, the i-th chain would be 10 * ans[i] + 0, 10 * ans[i] + 1, ………, 10 * ans[i] + 5.

The algorithm is as follows -

- Declare an ‘
**ans’**array and push 0 to 5 in it. - Iterate from
**i****=****0**to**N / 6**.- Iterate from
**j = 0 to 5:**- Append
**ans[i] * 10 + ans[j]**to**ans**, if**ans[i] * 10****!= 0**. - If ans[i] * 10 is 0 then we will be left with ans[j] and we have already inserted ans[j] in the and, hence there is no need to insert it again.

- Append

- Iterate from
- Finally, return ans[n - 1].

**Approach : **

If we have a number with a base of 10, then each digit of the number will be from 0 to 9. Similarly, if each digit of a number is from 0 to **X**, then the number can be represented in base X+1. Since a special number has digits from 0 to 5, and the special number series starts from 0, we observe that specialNumber(N) is equal to the base 6 representation of N - 1.

Hence to find the Nth special number it is sufficient to find the base 6 representation of N - 1. This can be done with the help of the following recursive formula.

specialNumber(N) = (N) % 6) + (10 * specialNumber((N) / 6)).

For example, the base 6 representation of 15 is 23, by repeatedly dividing N by 6 and storing the remainders.

15 base 6 = (15 % 6) + 10 * Base 6 representation of (15 / 6).

= 3 + (10 * Base 6 representation of (2))

= 3 + (10 * 2)

= 23

Here, digit 2 corresponds to 10^1-th power, and digit 3 corresponds to 10^0-th power.

The algorithm is as follows -

- First, subtract the number
**N**by 1. - Then, convert the number to base 6.
- Implement a recursive function
**specialNumber(N).** - If
**N < 6**, then our ‘ans’ is simply**N,**so return it. This will serve as the base case in our recursive function. - Else, return
**(N % 6) + (10 * specialNumber(N / 6))**. - Covert the number to base 6 by calculating the remainder and adding it again and again to get the result.

- Implement a recursive function