TopCoder

Thumb output jddoia
$\huge 南ことり$
不要再虐我了$ε=ε=ε=ε=ε=ε=┌(; ̄◇ ̄)┘$

User's AC Ratio

66.7% (24/36)

Submission's AC Ratio

32.0% (47/147)

Tags

Description

有一隻貓,叫做喔踢。她因為在背地裡對N老大不利,某天被N老大的騎士團抓到,而遭受慘無人道的酷刑...

「求求你別再考我了...」喔踢貓如此哀號道。

精神及肉體受到打擊的她,轉向警察局求助。背ㄍ...不是,根據喔踢貓的敘述,已知K騎士團中連續的團員們相乘(K團員們是自然數),會剛好是N老大的倍數。由於你不能濫抓無辜百姓,所以只能抓最少的K,來找到N老大。

以上敘述想講的是,請找到最小的K,使得K!是N的倍數。
註:0! = 1

Input Format

第一行輸入一個數字 Q
接著有Q行,每行輸入一個數字N
$( N \leq 5 \times 10 ^ 6, Q \leq 2 \times 10 ^ 5)$

Output Format

輸出能找到N老大,所需要的最少K團員數量。
也就是輸出最小的K使得K!是N的倍數。

Sample Input

4
1
8
13
169

Sample Output

0
4
13
26

Hints

Problem Source

Problem Set by jeeeerrrpop

Subtasks

No. Testdata Range Constraints Score
1 0~4 $N\leq 1000, Q \leq 1000$ 10
2 5~9 $N\leq 1000$ 20
3 10~15 $N \leq 2 \times 10 ^ 6 $ 57
4 16 無額外限制 13

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1
1 1000 262144 65536 1
2 1000 262144 65536 1
3 1000 262144 65536 1
4 1000 262144 65536 1
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 3
11 1000 262144 65536 3
12 1000 262144 65536 3
13 1000 262144 65536 3
14 1000 262144 65536 3
15 1000 262144 65536 3
16 1000 262144 65536 4