C - Circular Necklace Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君はビーズを円形に並べてネックレスを作ろうとしています。

ネックレスには合計 M 個のビーズが円形に等間隔で並んでおり、各ビーズには時計回りに 0 から M - 1 までの番号が付いています。

整数 k（1 \le k \le M - 1）を 1 つ選び、ビーズ 0 から出発して、毎回時計回りにちょうど k 個先のビーズへ進むことを繰り返します。訪れるビーズの番号の列は

0,\; k \bmod M,\; 2k \bmod M,\; 3k \bmod M,\; \dots

であり、再びビーズ 0 に到達した時点で終了します。すなわち、ik \bmod M = 0 となる最小の正整数を i とすると、訪れるビーズは

0,\; k \bmod M,\; 2k \bmod M,\; \dots,\; (i-1)k \bmod M

のちょうど i 個です（出発点のビーズ 0 は含み、戻ってきたビーズ 0 は含みません）。

ある k について、訪れるビーズの個数がちょうど M 個、すなわち 0 番から M-1 番までのすべてのビーズをちょうど一度ずつ訪れるとき、その k を 良い と呼びます。

M \ge 2 であり、かつ 1 \le k \le M - 1 を満たすすべての k が良いとき、M を 完全な個数 と呼びます。

高橋君は現在 N 個のビーズを持っています。高橋君は新しいビーズを追加することはできますが、ビーズを減らすことはできません。ネックレスのビーズの総数 M を完全な個数にするために追加すべきビーズの最小個数を求めてください。すなわち、M \ge N かつ M が完全な個数であるような最小の M に対して、M - N を出力してください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \leq T \leq 5000
  • 2 \leq N_i \leq 10^{12}
  • 入力はすべて整数である。

入力

T
N_1
N_2
\vdots
N_T

1 行目には、テストケースの個数 T が与えられる。続く T 行のうち i 行目には、i 番目のテストケースにおける現在のビーズの個数 N_i が与えられる。

出力

T 行出力せよ。i 行目には、i 番目のテストケースについて、追加すべきビーズの最小個数を出力せよ。

入力例 1

4
2
3
4
10

出力例 1

0
0
1
1

入力例 2

5
5
6
7
8
9

出力例 2

0
1
0
3
2

入力例 3

6
20
29
30
100
255
256

出力例 3

3
0
1
1
2
1

入力例 4

8
999983
1000000
9999991
123456789
999999937
9999999967
999999999989
1000000000000

出力例 4

0
3
0
2
0
0
0
39

入力例 5

1
2

出力例 5

0

Score : 366 pts

Problem Statement

Takahashi is trying to make a necklace by arranging beads in a circle.

The necklace has a total of M beads arranged at equal intervals in a circle, and each bead is numbered from 0 to M - 1 in clockwise order.

He chooses an integer k (1 \le k \le M - 1), starts from bead 0, and repeatedly moves to the bead exactly k positions ahead in the clockwise direction. The sequence of bead numbers visited is

0,\; k \bmod M,\; 2k \bmod M,\; 3k \bmod M,\; \dots

and the process ends when bead 0 is reached again. That is, letting i be the smallest positive integer such that ik \bmod M = 0, the beads visited are

0,\; k \bmod M,\; 2k \bmod M,\; \dots,\; (i-1)k \bmod M

which is exactly i beads (including the starting bead 0, but not including bead 0 upon return).

For a given k, if the number of beads visited is exactly M — that is, all beads from 0 to M-1 are visited exactly once — then k is called good.

If M \ge 2 and every k satisfying 1 \le k \le M - 1 is good, then M is called a perfect number (of beads).

Takahashi currently has N beads. He can add new beads but cannot remove any. Find the minimum number of beads he needs to add so that the total number of beads M in the necklace is a perfect number. In other words, find the smallest M such that M \ge N and M is a perfect number, and output M - N.

There are T test cases; find the answer for each of them.

Constraints

  • 1 \leq T \leq 5000
  • 2 \leq N_i \leq 10^{12}
  • All inputs are integers.

Input

T
N_1
N_2
\vdots
N_T

The first line contains the number of test cases T. The i-th of the following T lines contains N_i, the current number of beads for the i-th test case.

Output

Output T lines. The i-th line should contain the minimum number of beads to add for the i-th test case.

Sample Input 1

4
2
3
4
10

Sample Output 1

0
0
1
1

Sample Input 2

5
5
6
7
8
9

Sample Output 2

0
1
0
3
2

Sample Input 3

6
20
29
30
100
255
256

Sample Output 3

3
0
1
1
2
1

Sample Input 4

8
999983
1000000
9999991
123456789
999999937
9999999967
999999999989
1000000000000

Sample Output 4

0
3
0
2
0
0
0
39

Sample Input 5

1
2

Sample Output 5

0