CF1937B.Binary Path

You are given a $2 \times n$ 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$.

你有一个 $2 \times n$ 的网格，其中每个格子填有数字 $0$ 或 $1$。记第 $i$ 行第 $j$ 列处的数字为 $a_{ij}$。

一只蚱蜢起始于左上角格子 $(1, 1)$，每次只能向右或向下跳一格，目标是到达右下角格子 $(2, n)$。考虑该路径所经过的所有格子（按访问顺序）中的数字构成的长度为 $n+1$ 的二进制字符串。

你的任务是：

1. 通过选择任意一条可行路径，找出所能得到的字典序最小$^\dagger$ 的字符串；
2. 求出能产生该字典序最小字符串的路径条数。

$^\dagger$ 若两个字符串 $s$ 和 $t$ 长度相同，则当且仅当在 $s$ 与 $t$ 首次出现差异的位置上，$s$ 在该位置的字符严格小于 $t$ 在对应位置的字符时，称 $s$ 的字典序小于 $t$。

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

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

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

The third line of each test case contains a binary string $a_{21} a_{22} \ldots a_{2n}$ ($a_{2i}$ is either $0$ or $1$).

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）。

每个测试用例的第二行包含一个二进制字符串 $a_{11} a_{12} \ldots a_{1n}$（其中每个 $a_{1i}$ 为 $0$ 或 $1$）。

每个测试用例的第三行包含一个二进制字符串 $a_{21} a_{22} \ldots a_{2n}$（其中每个 $a_{2i}$ 为 $0$ 或 $1$）。

保证所有测试用例的 $n$ 之和不超过 $2 \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.

对于每个测试用例，输出两行：

1. 通过选择任意一条可用路径所能得到的字典序最小的字符串；
2. 能够产生该字符串的路径数量。

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

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

在第一个测试用例中，字典序最小的字符串是 $\mathtt{000}$。有两条路径可以得到该字符串：

在第二个测试用例中，字典序最小的字符串是 $\mathtt{11000}$。仅有一条路径可以得到该字符串：