Andrew 正在读七年级。班级最近学习了循环小数，Andrew 对如何处理它们非常好奇。

回想一下，循环小数是通过指定其无限小数表示中的非循环部分和循环部分来表示有理数的一种方式。例如，$1/7 = 0.(142857)$，$1/12 = 0.08(3)$。

有些数字有两种循环小数表示法，即那些实际上是有限小数的数字，例如 $0.(9) = 1.(0)$。在本题中，此类数字必须表示为以零结尾的形式，因此对于本题而言，$0.(9)$ 是不正确的循环小数表示。

现在 Andrew 想要将两个以循环小数形式给出的数字相加。两个循环小数的和仍然是一个循环小数，但循环节的长度可能非常大。因此，Andrew 只要求你求出和的某些特定位上的数字。你需要输出第 $a_1, a_2, \dots, a_n$ 位上的数字。

为了简化任务，Andrew 只要求将形式为 $0.(\omega)$ 的数字相加，其中 $\omega$ 是一个循环节。

输入格式

输入文件包含多个测试用例。输入文件的第一行包含 $t$，即测试用例的数量。

每个测试用例的前两行包含要相加的两个数字的循环节，循环节包含 $0$ 到 $9$ 的数字。每个循环节的长度最多为 $100\,000$。接下来的行包含 $n$，即查询的数量，随后的一行包含 $n$ 个整数 $a_i$ ($1 \le n \le 300\,000, 1 \le a_i \le 10^{18}$)。

输入文件中所有数字的循环节总长度不超过 $200\,000$。输入文件中 $n$ 的总和不超过 $300\,000$。

输出格式

对于每个测试用例中的每个 $a_i$，打印出两个循环小数之和在小数点后第 $a_i$ 位上的数字。位数从 $1$ 开始编号。

不要用空格分隔数字。每个测试用例的答案请打印在单独的一行上。

样例

样例输入 1

2
142857
3
10
1 2 3 4 5 6 7 8 9 10
4
5
3
1 2 3

样例输出 1

4761904761
000

说明

在第一个样例中，$0.(142857) = 1/7$，$0.(3) = 1/3$，$1/7 + 1/3 = 0.4761904761904761 \dots$

在第二个样例中，$0.(4) = 4/9$，$0.(5) = 5/9$，$4/9 + 5/9 = 1.00000000 \dots$