New TIOJ 新 TIOJ 已上線！舊 submission 已全數完成 rejudge，詳見公告。
Feature Change 現在所有新 submission 的 compiler 將預設為與前一次 submission 相同，敬請注意。
Feature Change 現在所有新 submission 的 compiler 將預設為與前一次 submission 相同，敬請注意。
2144 . 喔踢貓
TopCoder
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 1
4
1
8
13
169
1
8
13
169
Sample Output 1
0
4
13
26
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 |