The Factorial Conundrum

All submissions for this problem are available.
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^{20}
 1 ≤ N < 10^{30}
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.
Author:  Debanjan 
Tags  Debanjan 
Date Added:  21092013 
Time Limit:  1.12448 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 