FACTCN - The Factorial Conundrum
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 < 1020
- 1 ≤ N < 1030
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.
hide comments
nadstratosfer:
2018-07-28 02:31:59
Unless there's a very similar problem in classical, the presence of this one in tutorial section is a damn outrage. Took me 3 bloody hours to design the algorithm and push it past TLE. Unwanted bonus: 45mins of fighting WA just to find out the problem assumes that answer for 1 is 1. WTF!
|
|
Francky:
2015-01-24 19:02:00
@psetter :What happened to this problem ?
|
Added by: | :(){ :|: & };: |
Date: | 2014-02-21 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | own problem used in CODEWAR 2013 |