Little Omrita recently learned about factorials. Her teacher gave her a list of factorials of all the numbers starting from 1 to N. Omrita can choose any integer M, and she is supposed to compute the product of all the factorials starting from 1 i.e (1! * 2! * 3! * 4! * …) modulo M.

During her calculation, she noticed that no matter what M she choose before (at the start of the process) after a certain number of multiplication the answer becomes 0 and hence she can’t continue further.

She don't like this and wanted to know: for a chosen M what could be the maximum number of products she can compute before she has to stop. (See example for more clarification).

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.The first and the only line of each test case contains a single integer M denoting the number omrita had chosen.

Output

For each test case, output a single line containing the required answer.

Constraints

• 1 ≤ T ≤ 100
• 1 ≤ M < 10²⁰
• 1 ≤ N < 10³⁰

Example

Input: 
1
10

Output: 
4

Explanation

For the test case M = 10; First few terms in Omrita's list:

• 1! = 1
• 2! = 2
• 3! = 6
• 4! = 24
• 5! = 120
• 6! = 720
• 7! = 5040
• 8! = 40320
• ...

Omrita will proceed in the following manner:

• 1 * 2 = 2 MOD 10 = 2
• 2 * 6 = 12 MOD 10 = 2
• 2 * 24 = 48 MOD 10 = 8
• 8 * 120 = 960 MOD 10 = 0

So, she can perform 4 calculations.