Liquid Separation Challenge

Bessie has recently taken an interest in chemistry. She has two different colored liquids, denoted by 1 and 2, which do not mix with each other. In two test tubes, each containing a mixture of these two liquids of N units (with 1 ≤ N ≤ 10⁵), the liquids settle into layers – so that each tube can be represented as a string f1f2...fN and s1s2...sN (the first character is at the bottom). It is guaranteed that at least one unit of each color appears overall.

Bessie wishes to separate the liquids so that each test tube ends up containing units of exactly one color. To help her, she has an extra, empty beaker (with infinite capacity). She is allowed to perform the following operation: during one "pour", she removes from the top of a container (a test tube or the beaker) the entire contiguous block of liquid of some color i (i.e. the top block consisting of one color) and pours it onto the top of another container. Note that you cannot pour from a container into itself, and the source container must be non‐empty.

The goal is to separate the liquids so that the two test tubes each contain liquids of a single color (the specific color in each test tube does not matter), and the beaker is empty at the end. There are T test cases (1 ≤ T ≤ 10). In each test case an extra parameter P is given. Let M be the minimum number of pours required to achieve the goal.

• If P = 1, output only the number M.
• If P = 2, output an integer A (with M ≤ A ≤ M+5) on the first line indicating the number of moves in your scheme, and then output A lines describing a sequence of moves that takes exactly A pours.
• If P = 3, output M on the first line followed by M lines describing a sequence of moves that takes exactly M pours.

Note: Each move is printed as two numbers specifying the source container and the target container. The containers are numbered 1, 2 (the test tubes) and 3 (the beaker). The sequence of moves must be legal under the pouring rules.

Explanation of a valid strategy:

Since the order of layers in a tube is fixed (the liquid at the bottom never moves) and one may only remove the top contiguous block, the optimal strategy is forced by the structure of the mixtures. One valid method is to use the beaker as temporary storage: for each test tube not already homogeneous in a chosen final color, pour out all its blocks (one block per pour) into the beaker. Then, pour blocks from the beaker back into the appropriate test tube according to their color. In our solution we decide the final assignment as follows: we desire to end with tube 1 containing all units of color 1 and tube 2 all units of color 2, unless one of the tubes is already pure with the other color – in which case we swap the roles to minimize work. Each pour moves exactly one contiguous block. The total number of moves is therefore M = 2*(b₁ + b₂), where b_i is the number of blocks in tube i if it is not already in its desired final state, and zero otherwise.

inputFormat

The first line contains a single integer T (1 ≤ T ≤ 10).

For each test case, the input is given in the following order:

1. A line containing the integer P (which is 1, 2, or 3).
2. A line containing a nonempty string representing the first test tube (bottom to top).
3. A line containing a nonempty string representing the second test tube (bottom to top).

The length of each string is N (1 ≤ N ≤ 10⁵). It is guaranteed that at least one occurrence of '1' and one occurrence of '2' appear overall.

outputFormat

If P = 1, output a single integer M – the minimum number of pours needed.

If P = 2 or P = 3, on the first line output an integer A (with M ≤ A ≤ M+5 for P = 2 and A = M for P = 3) representing the number of moves in your plan. Then, output A lines each containing two integers separated by a space, representing the source container and the target container for that move.

sample

2
1
121
212
1
1111
2222

12

</p>