Von Neumann's squares

linked list two pointers random numbers classic

In 1949 John von Neumann proposed getting “random” numbers like this: take a d-digit number, square it, pad it with zeros on the left to 2d digits and take the middle d digits. That is the next number, and the same is done with it. From 0540 you get 2916 (the square is 00291600), then 5030, 3009, and 0540 again.

There are finitely many d-digit numbers, so the sequence is bound to repeat. First comes a tail of μ numbers that will never occur again, and after it a cycle of length λ spins for ever. Formally, μ is the smallest index from which the numbers repeat: x_μ occurs again, while x₀, …, x_μ−1 do not; λ is the smallest positive number with x_μ+λ = x_μ. For each seed find μ and λ.

Input

The first line holds t (1 ≤ t ≤ 300), the number of queries. Each of the next t lines holds an even d (2 ≤ d ≤ 8) and the seed x₀ (0 ≤ x₀ < 10^d). The sum of μ + λ over all queries of one test is at most 2·10⁵.

Output

For each query, μ and λ separated by a space, on a line of its own.

Examples

Example 1

Input

Output

0 4
101 4
7 1

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 8 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

Each number determines the next uniquely. So the sequence is a linked list whose “link to the next node” is a formula. How do you tell that the list has looped, and where exactly the ring begins?

2Hint 2

Waiting for x₀ to come back will not do: if the sequence has a tail, x₀ never occurs again. You can remember all the numbers in a dictionary; that is correct. But there is a way with O(1) memory: two pointers, one stepping one number at a time, the other two.

3The idea

Floyd’s algorithm, the tortoise and the hare. The tortoise makes a step x → f(x), the hare two. Once both are in the cycle, the hare gains one step on the tortoise per move and cannot jump over it, so they will meet. Then one is sent back to the start, and both go one step at a time: they meet exactly at the entrance to the cycle, after μ steps. Finally, go round the cycle from the entrance and count λ.

4Walkthrough

Why they meet. After μ steps the tortoise enters the cycle, and the hare is already there. Each move the distance between them along the cycle shrinks by one, and the hare cannot jump over the tortoise, so the meeting happens within λ moves. Let it happen after i steps of the tortoise: x_i = x_2i, and i ≥ μ. The hare went i more steps and ended up in the same place, so i is a multiple of λ.

Why the second stage leads to the entrance. Put pointer A at x₀, pointer B at the meeting place x_i, and let both step one at a time. After μ steps A stands at x_μ, at the entrance to the cycle, and B at x_i+μ, that is, i steps further along the cycle from the entrance; i is a multiple of λ, so this is the entrance too. They do not meet earlier: while A is on the tail, B is already in the cycle, and the tail’s numbers do not occur in the cycle. The number of steps until the meeting is μ.

The function itself: x * x // 10**(d/2) % 10**d. The division drops the lowest d/2 digits of the square, the remainder drops the highest. There is no need to pad with zeros as a string: in integers they are there by themselves. For d = 8 the square is below 10¹⁶ and fits in a 64-bit Go integer.

A dictionary “number → step index” also gives the answer in O(μ + λ), but keeps all the numbers of the tail and the cycle in memory. Here there are at most 10⁸ of them and the test is small, so a dictionary will pass. The pointers are indispensable when the state is huge and cannot be remembered: that is how Pollard’s rho method works, looking for a cycle modulo an unknown divisor of a number.

4+Solution

5Complexity

O(μ + λ) evaluations of f per query: in the first stage at most three per step of the tortoise, and the tortoise makes fewer than μ + λ steps before the meeting. Memory O(1).

6Common mistakes

Waiting for x₀ to return. On any number with a tail the loop is infinite.
The meeting place is the entrance. The tortoise and the hare meet somewhere inside the cycle. For 0540, which lies on a cycle of four numbers from the start, the first stage ends after 4 steps, while μ = 0.
The middle digits as a string without zeros. str(x * x) for 540 is “291600”, six digits, and its middle is different. Von Neumann padded with zeros on the left to 2d digits.
λ = 0 for a fixed point. 0 goes to 0, and its cycle has length 1, not 0.

Algorithms behind it

DS Data structure Linked list Nodes with links to neighbours: insertion and removal at a known node in O(1), the way to the k-th takes k steps. O(1) at a known node 2 problems NUM Algorithm Pseudorandom number generators Where “random” numbers come from, why a bad generator shows in its planes, and how to test one. O(1) per number 2 problems NUM Algorithm Pollard’s rho algorithm A divisor p of n in ~√p steps: a cycle modulo an unknown p, the tortoise and the hare, the gcd. O(√p) multiplications modulo n 1 problem