Ling: Stir, let's go out and play our favorite game.

Stir: I am already having fun with my first factorial program.

Ling: Than I will give you a challenge on factorials. If you fail in it, you will have to come.

Stir: ok..

Ling gives Stir a number x and the challenge is to find the largest value of n such that n! is not greater than the largest value that can be formed by x digits. Stir is stuck with the problem and needs your help. Now, it's your turn to make sure that Stir can continue having fun with factorials.

Input

The first line of the input contains a number t (about 10^5), the number of the test cases. The next t lines contain a number x (1 <= x <= 10^9).

Output

Output a total of t lines with each line containing the value n corresponding to the input case.

Example

Input: 
2
1
7

Output: 
3
10