How many bases lie

primes number theory counting

The Miller–Rabin test is wrong on a composite n only if the base chosen is a strong liar. Write n − 1 = 2^s·d with odd d. A base a (1 ≤ a ≤ n − 1) is a strong liar if a^d ≡ 1 (mod n) or a^2ⁱd ≡ −1 (mod n) for some i from 0 to s − 1. A base is a Fermat liar if aⁿ⁻¹ ≡ 1 (mod n).

To understand how dangerous a number is for the test, one wants to know how many liars of each kind it has. Trying all bases is impossible: the numbers go up to 4·10¹⁸. But for each number its prime factorisation is known.

For example, 2047 = 23 · 89 has 242 strong liars (among them 1, 2 and 2046) and 484 Fermat liars.

Input

The first line holds the number t (1 ≤ t ≤ 10,000). Each of the next t lines describes one number: first the number of distinct prime divisors k (1 ≤ k ≤ 15), then k pairs “prime p, exponent e” in increasing order of p. The number n = ∏ p^e is odd, composite and less than 2⁶².

Output

For each number, a line of two numbers: how many strong liars and how many Fermat liars there are among the bases from 1 to n − 1.

Examples

Example 1

Input

5
1 3 2
2 3 1 5 1
3 3 1 11 1 17 1
2 23 1 89 1
3 7 1 19 1 67 1

Output

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 6 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

A liar is necessarily coprime to n. By the Chinese remainder theorem, choosing a base modulo n is the same as choosing its remainder modulo each p^e independently. And a congruence modulo n holds when it holds modulo each p^e. How many solutions does a^d ≡ 1 have modulo a single p^e?

2Hint 2

The invertible remainders modulo p^e (for an odd prime p) form a cycle: they are all powers of one remainder g, a primitive root. There are φ(p^e) = p^e−1(p − 1) of them. In a cycle of length m the equation x^t = 1 has exactly gcd(t, m) solutions. And x^t = −1?

3Hint 3

The cases “a^d ≡ 1” and “a^2ⁱd ≡ −1” for different i do not overlap: after −1 the chain has only ones. So liars can be counted by case and added up.

4The idea

Count the solutions modulo each p^e and multiply; that is the Chinese remainder theorem. Let p − 1 = 2^s_p·d_p with odd d_p. Modulo p^e: a^d ≡ 1 has exactly gcd(d, d_p) solutions, and a^2ⁱd ≡ −1 has exactly 2ⁱ·gcd(d, d_p) if i < s_p, and none otherwise. Multiplying over all k primes and adding the cases gives Monier’s formula:

$$S(n) = \prod_p \gcd(d, d_p) \cdot \Bigl(1 + \sum_{i=0}^{\nu - 1} 2^{ik}\Bigr), \qquad F(n) = \prod_p \gcd(n - 1, p - 1),$$

where ν is the smallest of the s_p.

5Walkthrough

Why there are that many solutions. Let g be a primitive root modulo p^e, m = φ(p^e), and x = g^y. Then x^t = 1 means m | ty, and there are exactly gcd(t, m) suitable y from 0 to m − 1. The remainder −1 is g^m/2 (the only remainder of order 2), and x^t = −1 means ty ≡ m/2 (mod m). Such a congruence is solvable when gcd(t, m) divides m/2, and then it also has gcd(t, m) solutions.

Now substitute. The number p divides n, so it does not divide n − 1 or d, hence gcd(d, m) = gcd(d, d_p): the odd d takes nothing from the factor p^e−1 or from the twos in m. For t = 2ⁱd we get gcd(t, m) = 2^{min(i, s_p)}·gcd(d, d_p), while m/2 contains two to the power s_p − 1. The divisibility holds exactly when i < s_p. The same for Fermat liars: gcd(n − 1, m) = gcd(n − 1, p − 1).

By the Chinese remainder theorem a base is a liar when the required congruence holds modulo each p^e, and the remainders modulo different moduli are chosen independently. The case a^d ≡ 1 gives ∏ gcd(d, d_p) bases, the case a^2ⁱd ≡ −1 the product of 2ⁱ·gcd(d, d_p) over all k primes, that is, 2^ik·∏ gcd(d, d_p), if i is less than all the s_p, and zero otherwise. Add the cases i = 0, …, ν − 1.

A check on 2047 = 23 · 89: d = 1023, 22 = 2 · 11, 88 = 8 · 11, ν = 1, k = 2. S = 11 · 11 · (1 + 1) = 242, F = gcd(2046, 22) · gcd(2046, 88) = 22 · 22 = 484.

In Go everything fits in uint64: S and F are at most n, and the terms of the sum are powers of two at most 2^νk ≤ ∏ p ≤ n, because each p ≥ 2^ν + 1.

5+Solution

6Complexity

Per number, k runs of Euclid’s algorithm and computing n from the factorisation: O(k log n). Trying the bases would cost O(n log n), which for n around 10¹⁸ is billions of years.

7Common mistakes

Trying the bases. Correct, and fine for checking on numbers up to a few thousand, but hopeless on the large tests.
The forgotten one in the bracket. The term 1 is the bases with a^d ≡ 1, for example a = 1 itself. Without it 15 would have one liar, while it has two: 1 and 14.
Prime powers. For p^e it is tempting to take gcd(d, φ(p^e)), and that is right, simply because the factor p^e−1 has no common divisors with d. But gcd(n − 1, p^e − 1) instead of gcd(n − 1, p − 1) is already a mistake.
ν by the exponent of n − 1. The sum goes up to the smallest s_p, not up to s: for i ≥ s_p there are no solutions modulo that p^e.

Algorithms behind it

NUM Algorithm The Miller–Rabin test Primality in k modular exponentiations: base-witnesses catch a composite, and liars make up at most a quarter. O(k log³ n) 2 problems NUM Algorithm Chinese remainder theorem A number from its residues modulo several moduli: Garner's algorithm and exact computation over many primes. O(k²) operations on machine numbers 2 problems NUM Algorithm Euclid's algorithm The greatest common divisor of two numbers in O(log n) divisions with remainder. O(log min(a, b)) 2 problems