Saaho and Dream Girl clashes at the box office.Saaho is a big budget movie as compared to Dream girl So Saaho started well at the Box office. Total collections of Saaho at the end of $N$^th day at the box office is given by $A^N$.As the review of Dream Girl is positive, Its collection pick up day by day and the total collections of Dream Girl at the end of $N$^th day at the box office is given by $N!$. Find minimum number of days at the box office in which Dream girl collection crosses the Saaho collection.

Input
The first line of the input contains number $T (1<=T<=10^5)$, the number of testcases.
Each test case consists of a single number $A (2<=A<=10^6)$.

Output
For each test cases print the minimum number of days in new line.