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

  • 1T100
  • 1M < 1020
  • 1N < 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!

But seriously, this needs to be in classical.

Francky: 2015-01-24 19:02:00

@psetter :What happened to this problem ?
Why available today ? Please explain.

==

By the way : the constraint about N is unnecessary, should be removed.

Last edit: 2015-01-24 19:02:55

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