FUNFACT - Factorial challenge

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

Added by:Siddharth Kothari
Date:2010-09-23
Time limit:2.412s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own problem

hide comments
2016-07-26 07:36:49
Oh, I didn't know that Stirling's Approximation is very near to correct answer, but I realized that it is so good.
2015-01-10 18:42:26 Sahil Sharma
Wow, a very nice problem. Requires some mathematical knowledge! :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.