Ent Numbers

Time limit1sMemory limit128 MB

Summary

Simulate a Goodstein-like sequence where each step subtracts one, then raises the base while keeping digits, and report the base where the term first hits 0 or that it exceeds 2^60.

Level: Medium7 of 10
Topics: Implementation, Math, Simulation
Solved: No attempts yet

Problem

Ents are a race of tree-like beings in Middle-earth, the ancient shepherds of the forest. When Bilbo visits the forest of Fangorn to meet the Ents, he notices some very, very long numbers in their writings and asks Treebeard (the eldest of the Ents) about them. Treebeard explains that the numbers describe the convergence rates of certain sequences (introduced to the Ents by a mathematician named Reuben Goodstein). After a few days of explanation, Bilbo finally understands how these numbers are generated.

Consider a sequence defined by two numbers, $N$ and $B$ . The first term of the sequence is $N$ itself, written in base $B$ . To obtain the next term, we decrease the number by 1 and then, keeping the resulting digits unchanged, increase the base $B$ by 1.

For example, start with $N = 42$ and $B = 10$ . We group each digit in parentheses and write it as (4)(2) Base 10. The next term is (4)(1) Base 11, which equals 45 in base 10: we first subtract one (giving (4)(1) Base 10) and then raise the base by one while keeping the same digits. The term after that is (4)(0) Base 12, i.e. 48 in base 10. The table below shows how the sequence continues.

B	N in base B	N in base 10	Explanation
10	(4)(2)	42	The sequence is defined by the two starting numbers.
11	(4)(1)	$4 \times 11 + 1 = 45$
12	(4)(0)	$4 \times 12 + 0 = 48$
13	(3)(11)	$3 \times 13 + 11 = 50$	We subtract 1 first (in the previous base), then raise the base.
14	(3)(10)	$3 \times 14 + 10 = 52$
15	(3)(9)	$3 \times 15 + 9 = 54$

Although it looks like the sequence will keep growing, it eventually reaches zero at base $B = 192$ (the term goes to (1) Base 191, and then to (0) Base 192). The next table shows the sequence for a different starting point. As you can see, it can grow extremely fast (at base 100 the term already reaches 1000707070428).

B	N in base B	N in base 10
2	(1)(1)(0)(0)(1)(0)(0)	100
3	(1)(1)(0)(0)(0)(1)(1)	976
4	(1)(1)(0)(0)(0)(1)(0)	5124
5	(1)(1)(0)(0)(0)(0)(3)	18753
6	(1)(1)(0)(0)(0)(0)(2)	54434
7	(1)(1)(0)(0)(0)(0)(1)	134457

Treebeard explains that this sequence always reaches zero, even though it may first blow up to enormous values. Bilbo finds this hard to believe and asks for your help. Given the two starting numbers $N$ and $B$ , determine whether the sequence reaches 0 before the base reaches $2^{60}$ (about the largest number Bilbo can imagine), and if so, at which base it becomes zero.

Input

The first line contains the number of test cases $T$ ( $T < 100$ ). Each of the following $T$ lines contains two integers $N$ and $B$ (the starting number and the starting base, with $B \ge 2$ ), separated by a single space.

Output

For each test case, output one line. If the sequence reaches 0 before the base reaches $2^{60}$ , print

Starting with N = <N> and B = <B>, sequence converges to 0 at Base <base>.

where <base> is the base at which the term first becomes 0. Otherwise, print

Starting with N = <N> and B = <B>, sequence did not converge to 0 before 2^60.

Examples1

Example 1

Input

Expected output

Starting with N = 42 and B = 10, sequence converges to 0 at Base 192.
Starting with N = 100 and B = 2, sequence did not converge to 0 before 2^60.
Starting with N = 12 and B = 10, sequence converges to 0 at Base 24.
Starting with N = 15 and B = 8, sequence converges to 0 at Base 30.
Starting with N = 20 and B = 5, sequence converges to 0 at Base 80.