TopCoder

weyryafjnm;

erfvjuaweikm

User's AC Ratio

79.2% (38/48)

36.3% (81/223)

有一隻貓，叫做喔踢。她因為在背地裡對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的倍數。

4
1
8
13
169

0
4
13
26

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
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

Submit

Status