有一隻貓,叫做喔踢。她因為在背地裡對N老大不利,某天被N老大的騎士團抓到,而遭受慘無人道的酷刑...
「求求你別再考我了...」喔踢貓如此哀號道。
精神及肉體受到打擊的她,轉向警察局求助。背ㄍ...不是,根據喔踢貓的敘述,已知K騎士團中連續的團員們相乘(K團員們是自然數),會剛好是N老大的倍數。由於你不能濫抓無辜百姓,所以只能抓最少的K,來找到N老大。
以上敘述想講的是,請找到最小的K,使得K!是N的倍數。
註:0! = 1
第一行輸入一個數字 Q
接著有Q行,每行輸入一個數字N
$( N \leq 5 \times 10 ^ 6, Q \leq 2 \times 10 ^ 5)$
輸出能找到N老大,所需要的最少K團員數量。
也就是輸出最小的K使得K!是N的倍數。
Problem Set by jeeeerrrpop
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 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 262144 | 65536 | |
1 | 1000 | 262144 | 65536 | |
2 | 1000 | 262144 | 65536 | |
3 | 1000 | 262144 | 65536 | |
4 | 1000 | 262144 | 65536 | |
5 | 1000 | 262144 | 65536 | |
6 | 1000 | 262144 | 65536 | |
7 | 1000 | 262144 | 65536 | |
8 | 1000 | 262144 | 65536 | |
9 | 1000 | 262144 | 65536 | |
10 | 1000 | 262144 | 65536 | |
11 | 1000 | 262144 | 65536 | |
12 | 1000 | 262144 | 65536 | |
13 | 1000 | 262144 | 65536 | |
14 | 1000 | 262144 | 65536 | |
15 | 1000 | 262144 | 65536 | |
16 | 1000 | 262144 | 65536 |