#P1937B. Binary Path

    ID: 10383 Type: RemoteJudge 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: 4 Uploaded By: Tags>dpgreedyimplementation*1300

Binary Path

Description

You are given a 2×n2 \times n grid filled with zeros and ones. Let the number at the intersection of the ii-th row and the jj-th column be aija_{ij}.

There is a grasshopper at the top-left cell (1,1)(1, 1) that can only jump one cell right or downwards. It wants to reach the bottom-right cell (2,n)(2, n). Consider the binary string of length n+1n+1 consisting of numbers written in cells of the path without changing their order.

Your goal is to:

  1. Find the lexicographically smallest^\dagger string you can attain by choosing any available path;
  2. Find the number of paths that yield this lexicographically smallest string.

^\dagger If two strings ss and tt have the same length, then ss is lexicographically smaller than tt if and only if in the first position where ss and tt differ, the string ss has a smaller element than the corresponding element in tt.

Each test contains multiple test cases. The first line contains the number of test cases tt (1t1041 \le t \le 10^4). The description of the test cases follows.

The first line of each test case contains a single integer nn (2n21052 \le n \le 2 \cdot 10^5).

The second line of each test case contains a binary string a11a12a1na_{11} a_{12} \ldots a_{1n} (a1ia_{1i} is either 00 or 11).

The third line of each test case contains a binary string a21a22a2na_{21} a_{22} \ldots a_{2n} (a2ia_{2i} is either 00 or 11).

It is guaranteed that the sum of nn over all test cases does not exceed 21052 \cdot 10^5.

For each test case, output two lines:

  1. The lexicographically smallest string you can attain by choosing any available path;
  2. The number of paths that yield this string.

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1t1041 \le t \le 10^4). The description of the test cases follows.

The first line of each test case contains a single integer nn (2n21052 \le n \le 2 \cdot 10^5).

The second line of each test case contains a binary string a11a12a1na_{11} a_{12} \ldots a_{1n} (a1ia_{1i} is either 00 or 11).

The third line of each test case contains a binary string a21a22a2na_{21} a_{22} \ldots a_{2n} (a2ia_{2i} is either 00 or 11).

It is guaranteed that the sum of nn over all test cases does not exceed 21052 \cdot 10^5.

Output

For each test case, output two lines:

  1. The lexicographically smallest string you can attain by choosing any available path;
  2. The number of paths that yield this string.

Sample Input 1

3
2
00
00
4
1101
1100
8
00100111
11101101

Sample Output 1

000
2
11000
1
001001101
4

Note

In the first test case, the lexicographically smallest string is 000\mathtt{000}. There are two paths that yield this string:

In the second test case, the lexicographically smallest string is 11000\mathtt{11000}. There is only one path that yields this string: