# Count Special Numbers

#### A positive integer is called a Special Number if all the digits in its decimal representation lie between 1 to 5 (both inclusive). For example : 245, 312, etc. are some special numbers, whereas 340, 17, 0, etc. are some non-special numbers.

#### Given an integer 'N' . Your task is to find how many special numbers lie between 1 to N.

#### Input Format :

```
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first and only line of each test case contains the integer 'N'.
```

#### Output Format :

```
For each test case, print an integer denoting the total count of special numbers between 1 to N.
Print the output of each test case in a new line.
```

#### Note :

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

#### Constraints :

```
1 <= T <= 10^4
1 <= N <= 10^9
Time Limit: 1 sec
```

The idea is to iterate through all the numbers that are smaller than or equal to **N **one by one and find the total count of special numbers. To check whether a particular number is a special number, we can check the number digit by digit to determine whether all the digits lie between 1 to 5. If yes, then the number is a special number. Otherwise, the number is not a special number.

**Steps:**

- Define a variable
**specialNumbersFound**to store the total count of special numbers. Initialize it as 0. - Iterate from
**i = 1**to**N**- If
**i**is a special number, then increment**specialNumbersFound**by 1.- To check whether a number is a special number, we will write a boolean function that takes an integer
**K**as an argument and returns**True**if**K**is a special number, otherwise, it returns**False.** - Working of the
**checkSpecialNumber**function - While
**K**is greater than 0- Define
**rem**as**K % 10**to store the current rightmost digit of**K.** - If
**rem**does not lie between 1 to 5, then we will return**False.** - Set
**K**as**K / 10**.

- Define
- If we have not returned
**False**till now, then we will return**True**as all the digits we traversed were between 1 to 5. This means that**K**is a special number.

- To check whether a number is a special number, we will write a boolean function that takes an integer

- If
- Return the
**specialNumbersFound**variable.

**The total number of d - digit numbers that are special is 5^d **

For a **d - digit** number, each digit can have 5 possible values, i.e., 1, 2, 3, 4, and 5. The choice for any digit is independent of all the other digits. Therefore, by the rule of Product, we can infer that the total number of **d - digit** special numbers is **5^d.**

Let **N = N1 N2 … N(d-1) N(d) **be a **d - digit **number.

We can easily count and add all the **1 digit**, **2 digit … , d - 1 digit **special numbers using the above formula. The sum obtained will be **sum(5^i)** for **i = 1** to **d - 1**, which we can calculate naively or use the fact that the above sequence forms a Geometric Progression to obtain the result as **(5*(5^(d-1)-1))/4.** Let the obtained result be **res**.

Now it remains only to count the **d - digit **special numbers that are smaller than **N, **for which we will be using Digit - DP.

**Steps: **

- Let each digit of
**N**is stored in an array called**digits** - Initialize
**specialNumbersFound**as 0. - Iterate through
**i = 0**to**d - 1**- If
**i**is equal to**d - 1**, then we will add the minimum value among 5 and**digits[d-1]**to**specialNumbersFound**, and end the loop. This serves as the base case. - If
**digits[i]**is 0, then we will end the loop, as the current digit is 0, and now no special number exists, which has not been calculated till now. - Otherwise, if
**digits[i]**is greater than 5, then we will add**5^(d-i)**to**specialNumbersFound**, and end the loop. We are ending our process here because the current digit is greater than 5, and we have already added the count of special numbers having**i'th**digit less than or equal to 5. Hence, we need not go forward. - Otherwise add
**(digits[i]-1)*(5^(d-i-1))**to**specialNumbersFound**variable, and move forward. In this case, we are not breaking because we have only found the special numbers whose**i'th**digit is smaller than**digits[i],**but we have not found the count of special numbers whose**i'th**digit is equal to**digits[i].**

- If

Our final answer will be the sum of **res **and **specialNumbersFound** variable.