SPOJ Problem Set (classical) 5161. Factorial vs Power Problem code: FACVSPOW

Consider two integer sequences f(n) = n! and g(n) = aⁿ, where n is a positive integer. For any integer a > 1 the second sequence is greater than the first for a finite number of values. But starting from some integer k, f(n) is greater than g(n) for all n >= k. You are to find the least positive value of n for which f(n) > g(n), for a given positive integer a > 1.

Input

The first line of the input contains number t – the amount of tests. Then t test descriptions follow. Each test consist of a single number a.

Constraints

1 <= t <= 100000
2 <= a <= 10⁶

Output

For each test print the least positive value of n for which f(n) > g(n).

Example

Input:
3
2
3
4

Output:
4
7
9

---

Added by:	Spooky
Date:	2009-11-01
Time limit:	2s
Source limit:	50000B
Languages:	All except: TECS
Resource:	Advancement Autumn 2009, http://sevolymp.uuuq.com/