Zayin 和 Taotao 的数学很差。为了提高数学水平，他们今天一起数数。他们每秒钟按升序写下一个数字，例如 0, 1, 2, 3 等。然而，他们无法识别所有的阿拉伯字母。因此，他们都会忽略包含他们不认识的阿拉伯字母的数。例如，如果 Zayin 只认识 0 和 1，他会写下 0, 1, 10, 11 等。

对于每个阿拉伯字母，你都知道 Zayin 和 Taotao 是否能识别它。Zayin 和 Taotao 至少都能识别两个阿拉伯字母。此外，你知道 Zayin 在第 $x$ 秒会写下的数字。你能写一个程序来计算 Taotao 在同一时间会写下的数字吗？

输入格式

第一行包含一个整数 $T(1 \le T \le 10^4)$，表示测试用例的数量。

对于每个测试用例，第一行包含一个长度为 10 的字符串，表示 Zayin 能识别的阿拉伯字母集合。如果字符串的第 $i$ 个字符为 '1'（索引从 0 开始），则 Zayin 可以识别阿拉伯字母 $i$。否则，Zayin 无法识别阿拉伯字母 $i$。

类似地，第二行包含一个长度为 10 的字符串，表示 Taotao 能识别的阿拉伯字母集合。如果字符串的第 $i$ 个字符为 '1'（索引从 0 开始），则 Taotao 可以识别阿拉伯字母 $i$。如果为 '0'，则 Taotao 无法识别阿拉伯字母 $i$。

第三行包含 Zayin 在第 $x$ 秒写下的数字 ($x \le 2^{64}$)。

输出格式

对于每个测试用例，请在单行中输出 Taotao 在第 $x$ 秒会写下的数字。

样例

输入格式 1

1
1010000000
1100000000
20

输出格式 1

10