给你一个 $$$2 \times n$$$ 的网格,其中充满了零和一。令第 $$$i$$$ 行和第 $$$j$$$ 列的交叉点处的数字为 $$$a_{ij}$$$。
左上角的单元格 $$$(1, 1)$$$ 处有一只蚱蜢,它只能向右或向下跳一个单元格。它想要到达右下角的单元格$$$(2, n)$$$。考虑长度为 $$$n+1$$$ 的二进制字符串,该字符串由写入路径单元格中的数字组成,且不更改其顺序。
您的目标是:
1. 通过选择任意可用路径找到按字典顺序最小的$$$^\dagger$$$字符串;
2. 找出产生该字典顺序最小字符串的路径数。
$$$^\dagger$$$ 如果两个字符串 $$$s$$$ 和 $$$t$$$ 具有相同的长度,则 $$$s$$$ 按字典顺序小于 $$$t$$$ 当且仅当在 $$$s$$$ 和 $$$t$$$ 不同的第一个位置,字符串 $$$s$$$ 的元素比 $$$s$$$ 中的相应元素小$$$t$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,输出两行:
1. 通过选择任何可用路径可以获得的按字典顺序排列的最小字符串;
2. 产生该字符串的路径数。
示例
输入 #1
3 2 00 00 4 1101 1100 8 00100111 11101101
输出 #1
000 2 11000 1 001001101 4
注意
在第一个测试用例中,字典顺序最小的字符串是 $$$\mathtt{000}$$$。有两条路径可以产生该字符串:
在第二个测试用例中,字典顺序最小的字符串是 $$$\mathtt{11000}$$$。只有一条路径可以生成该字符串: