← Home
write a go solution for Description:
You are given a 2xn grid filled with zeros and ones. Let the number at the intersection of the i-th row and the j-th column be a_ij.

There is a grasshopper at the top-left cell (1,1) that can only jump one cell right or downwards. It wants to reach the bottom-right cell (2,n). Consider the binary string of length n+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 s and t have the same length, then s is lexicographically smaller than t if and only if in the first position where s and t differ, the string s has a smaller element than the corresponding element in t.

Input Format:
Each test contains multiple test cases. The first line contains the number of test cases t (1<=t<=10^4). The description of the test cases follows.

The first line of each test case contains a single integer n (2<=n<=2*10^5).

The second line of each test case contains a binary string a_11a_12ldotsa_1n (a_1i is either 0 or 1).

The third line of each test case contains a binary string a_21a_22ldotsa_2n (a_2i is either 0 or 1).

It is guaranteed that the sum of n over all test cases does not exceed 2*10^5.

Output Format:
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.

Note:
In the first test case, the lexicographically smallest string is mathtt000. There are two paths that yield this string:

In the second test case, the lexicographically smallest string is mathtt11000. There is only one path that yields this string:. Output only the code with no comments, explanation, or additional text.