This is a run-twice (communication) problem.

The Left Can and the Right Can are catching a dangerous criminal hiding in the streets of Iron City. However, since they can only sing AND deny what is happening, they also need someone who is good at XOR.

The Prefect of the Unit's Bureau (PUB) is carrying out an important mission to train his agents, LCB and RCB. For this purpose, he will run a series of tests with them. Each test consists of two stages. During a test, the agents cannot communicate directly with each other.

In the first stage, LCB receives an integer $$$n$$$ and a binary string $$$s$$$ of length $$$n - 1$$$. LCB must output a connected undirected graph on vertices $$$1, 2, \ldots, n$$$, without self-loops or multiple edges.

After receiving the graph from LCB, PUB may apply the following operation to it any number of times (possibly zero):

• choose an integer $$$k$$$ ($$$k \ge 2$$$) and a simple$$$^{\text{∗}}$$$ path $$$v_1, v_2, \ldots, v_{2k}$$$, consisting of $$$2k$$$ vertices and $$$2k - 1$$$ edges;
• choose any index $$$i$$$ ($$$1 \le i \le 2k-1$$$) and remove the edge between vertices $$$v_i$$$ and $$$v_{i+1}$$$ from the graph;
• if there is no edge between vertices $$$v_1$$$ and $$$v_{2k}$$$, add it.

Note that the number of edges may decrease after an operation. It can be shown that the graph remains connected.

Before passing the graph to RCB, PUB may arbitrarily reorder the edges and swap the two endpoints of any edge. This is possible even if PUB performs no operations.

In the second stage, PUB gives the resulting graph to RCB. RCB must recover the original string $$$s$$$. Find a strategy for both agents that succeeds regardless of the operations performed by PUB.

Your program will be run twice on each test: first as LCB, then as RCB. These are separate executions; the program's memory is not preserved between them.

First Run

Input

The first line contains the string first, indicating that this is the first run.

After this line, the remaining input has the following format.

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$3 \le n \le 10^3$$$) — the number of vertices.

The second line contains a string $$$s$$$ of length $$$n - 1$$$, consisting only of the characters 0 and 1.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^3$$$.

Output

For each test case, output an integer $$$m$$$ ($$$n - 1 \le m \le \frac{n(n - 1)}{2}$$$) — the number of edges in your graph. In each of the next $$$m$$$ lines, output two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), describing an edge.

The graph must be connected and contain no self-loops or multiple edges. You may output the edges and their endpoints in any order.

Second Run

Input

The first line contains the string second, indicating that this is the second run.

After this line, the remaining input has the following format.

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The value of $$$t$$$ is the same as on the first run, although the test cases may appear in a different order.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 10^3$$$; $$$n - 1 \le m \le \frac{n(n - 1)}{2}$$$) — the number of vertices and edges in the resulting graph. The value of $$$n$$$ is the same as in the corresponding test case of the first run.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), describing an undirected edge.

The edges may be listed in any order, and the two endpoints of each edge may be given in either order, even if PUB performs no operations. These orders need not match your output in the first run.

It is guaranteed that the graph is obtained from your graph in the first run by applying the operations described above zero or more times. It can be shown that the resulting graph is connected and contains no self-loops or multiple edges.

Output

For each test case, output the original binary string $$$s$$$ of length $$$n - 1$$$.