Problems Base course RU

The zero cells of a factorial

A big number is stored as an array of “digits” in a large base b, lowest first: in Python b = 2³⁰, in olympiad programs often 10⁹ or 10⁴. The article on big-number arithmetic shows that the first 33 cells of 1000! in base 2³⁰ are zeros: these are the trailing zeros of the number written in base 2³⁰. In base 10⁹ there are 27 such cells, and in ordinary decimal notation 1000! ends in 249 zeros.

How many zero low cells does n! have in base b? In other words, how many zeros does n! end with when written in base b? The factorial itself need not be computed, and could not be: n goes up to 10¹⁸.

Input

The first line holds the number of queries t (1 ≤ t ≤ 100). Each of the following lines holds two integers n and b (1 ≤ n ≤ 10¹⁸, 2 ≤ b ≤ 10¹²).

Output

For each query, the number of trailing zeros of n! written in base b.

Examples

Example 1

Input

4
1000 1073741824
1000 1000000000
1000 10
10 10

Output

Limits

Time · Python: 6000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 7 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 number written in base b ends in k zeros exactly when it is divisible by b^k. For b = 10 this is a well-known problem: there are as many zeros as there are fives in the factorisation of n!. Why fives, not twos?

2Hint 2

How many times does a prime p divide n!? Each multiple of p among the numbers 1…n contributes one factor, each multiple of p² one more, each multiple of p³ another. And if b = 2¹⁰·3, which runs out first, the twos or the threes?

3The idea

Factorise b = p₁^a₁·…·p_m^a_m. Let the prime p_i divide n! with exponent v_i; by Legendre’s formula v = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + … Then b^k divides n! as long as k·a_i ≤ v_i for all i, and the answer is min ⌊v_i/a_i⌋.

4Walkthrough

Factorise b by trial division by the primes up to 10⁶ (a sieve supplies them in advance): if something is left after that, it is a prime greater than a million, since a number up to 10¹² cannot have two such factors. For each prime compute the Legendre exponent: add up ⌊n/p⌋, ⌊n/p²⌋, … In Go it is handier to divide n by p again and again than to raise p to powers: that way there is no overflow with n around 10¹⁸.

Why Legendre’s formula is correct: among the numbers 1…n, exactly ⌊n/p^j⌋ are divisible by p^j. A number in which p occurs to the power e is counted in the terms j = 1, …, e, once in each, that is, exactly e times.

For 1000! in base 2³⁰: two divides it 500 + 250 + 125 + … = 994 times, and ⌊994/30⌋ = 33 zero cells. In base 10⁹ = 2⁹·5⁹: there are 249 fives and 994 twos, and the answer is min(⌊994/9⌋, ⌊249/9⌋) = 27. And in Go and V8, where the base is 2⁶⁴, there would be ⌊994/64⌋ = 15 zero words.

4+Solution

5Complexity

Factorising b takes up to 78,498 trial divisions; the Legendre exponent, O(log_p n) divisions per prime. Per query, O(π(10⁶) + log n).

6Common mistakes

“The largest prime runs out first.” For 10 that is true, but not always: 100! in base 3072 = 2¹⁰·3 has 97 twos and 48 threes, and ⌊97/10⌋ = 9 zeros, not 48.
A forgotten exponent. In base 12 = 2²·3 the twos are used up in pairs: v₂ must be divided by 2.
Overflow. p^j with n ≈ 10¹⁸ and a large p goes beyond 64 bits if you multiply first and compare afterwards.

Algorithms behind it

NUM Algorithm Big integers Numbers longer than a machine word: digits in base 10⁹ or 2³⁰, carries, column methods and expensive printing. addition O(n), column multiplication and division O(n²), printing in decimal O(n²) or O(M(n) log n) 2 problems NUM Algorithm The sieve of Eratosthenes All primes up to n in O(n log log n): cross out the multiples of each prime, starting from its square. O(n log log n) 2 problems