Overview

The essence of this problem is that a perfect count \(M\) is exactly a prime number. Therefore, for each test case, we find the smallest prime \(M\) that is at least \(N\), and the answer is \(M - N\).

Analysis

First, for a fixed \(M\) and \(k\), let’s consider how many beads are visited.

The visited beads are \(0, k \bmod M, 2k \bmod M, 3k \bmod M, \dots\)

We return to \(0\) when, for some positive integer \(i\), \(ik \equiv 0 \pmod{M}\). The smallest such \(i\) is actually determined by the greatest common divisor of \(k\) and \(M\).

Let \(g = \gcd(M, k)\), and write \(M = gM'\), \(k = gk'\), where \(\gcd(M', k') = 1\). Then

\(ik \equiv 0 \pmod{M}\)

is equivalent to

\(M \mid ik\)

which means

\(gM' \mid igk' \iff M' \mid ik'\)

Since \(\gcd(M', k') = 1\), we need \(M' \mid i\). Therefore the smallest \(i\) is \(M'\), that is

\(i = \dfrac{M}{\gcd(M, k)}\)

In other words, the number of beads visited is

\(\dfrac{M}{\gcd(M, k)}\)

From this, we can derive an important fact:

• All \(M\) beads are visited exactly once \(\iff \dfrac{M}{\gcd(M, k)} = M\)
• This is equivalent to \(\iff \gcd(M, k) = 1\)

That is, \(k\) being good is equivalent to \(\gcd(M, k) = 1\).

---

Next, let’s consider the condition for \(M\) to be a perfect count.

A perfect count means that all \(k\) with \(1 \le k \le M - 1\) are good, i.e.,

“For all \(k\), \(\gcd(M, k) = 1\)”

holds.

This is equivalent to \(M\) being a prime number.

• If \(M\) is prime, then every \(k\) with \(1 \le k \le M - 1\) is coprime to \(M\).
• If \(M\) is composite, then it has a divisor \(d\) with \(1 < d < M\), so setting \(k = d\) gives \(\gcd(M, k) = d > 1\), meaning \(k\) is not good.

Therefore, perfect counts are limited to primes, and every prime is a perfect count.

---

Examples

• When \(M = 5\): \(5\) is prime, so \(k = 1, 2, 3, 4\) are all good.
• When \(M = 6\): \(6\) is composite. For example, with \(k = 2\): \(0 \to 2 \to 4 \to 0\) Only \(3\) beads are visited. Therefore it is not perfect.

---

Why a naive approach doesn’t work

A straightforward approach would be:

• For each \(M\),
• Try all \(k\),
• Actually trace through the sequence.

However, this is extremely slow. Since \(N\) can be up to \(10^{12}\), it is far too slow.

Moreover, even if we can reduce “checking if perfect” to primality testing, trial division up to \(\sqrt{M}\) for each case is also heavy, given that the number of test cases can be up to \(5000\).

Therefore, this code uses Miller-Rabin primality testing for fast primality checks. Furthermore, the set of bases used is deterministic for 64-bit integers, so there are no false results for this problem.

Algorithm

For each test case, we proceed as follows:

1. Find the smallest prime \(M\) that is at least \(N\)
2. Output \(M - N\) as the answer

The method to find the prime \(M\) is as follows:

• If \(N \le 2\), then \(2\)
• Otherwise, if \(N\) is even, first set it to \(N + 1\)
• Then check only odd numbers in sequence, and take the first one that is prime

Primality testing uses is_prime.

Flow of is_prime(n)

1. First check if \(n\) is divisible by small primes
2. Otherwise, use Miller-Rabin to determine primality
3. The bases used are \(2, 325, 9375, 28178, 450775, 9780504, 1795265022\) — these 7 bases are deterministic for 64-bit integers

Since \(N \le 10^{12}\) in this problem, this runs sufficiently fast.

Complexity

• Time complexity: approximately \(O(g \log^3 N)\) per test case, where \(g\) is the gap between \(N\) and the smallest prime at least \(N\). (Evaluated using the bit complexity of a single Miller-Rabin round)
• Space complexity: \(O(1)\)

※ In practice, Miller-Rabin uses only a fixed number of bases, so it is very fast.

Implementation Notes

• The key insight is reducing the problem to primality testing rather than directly checking “perfect counts”.

• In next_prime, since no even number other than \(2\) is prime, we only need to check odd numbers.

• Using Python’s pow(a, d, n) allows fast computation of \(a^d \bmod n\).

• The 7 bases used for Miller-Rabin provide completely correct results for 64-bit integers — this is not randomized but deterministic.

  Source Code

import sys

def is_prime(n: int) -> bool:
    if n < 2:
        return False
    small_primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)
    for p in small_primes:
        if n % p == 0:
            return n == p

    d = n - 1
    s = 0
    while d % 2 == 0:
        s += 1
        d //= 2

    # Deterministic for 64-bit integers
    for a in (2, 325, 9375, 28178, 450775, 9780504, 1795265022):
        if a % n == 0:
            continue
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(s - 1):
            x = (x * x) % n
            if x == n - 1:
                break
        else:
            return False
    return True

def next_prime(n: int) -> int:
    if n <= 2:
        return 2
    if n % 2 == 0:
        n += 1
    while not is_prime(n):
        n += 2
    return n

def main():
    input = sys.stdin.readline
    T = int(input())
    ans = []
    for _ in range(T):
        N = int(input())
        M = next_prime(N)
        ans.append(str(M - N))
    print("\n".join(ans))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.