给你一个最简分数 $\frac{a}{b}$（即 $\gcd(a, b) = 1$）。每一秒，分子和分母都会同时增加 $1$，然后该分数会立即约分为最简形式。

具体来说，如果当前的分数是 $\frac{a}{b}$，一秒后它会变成 $\frac{a+1}{b+1}$。令 $g = \gcd(a + 1, b + 1)$，然后将其更新为 $\frac{(a+1)/g}{(b+1)/g}$。

给定初始分数 $\frac{a}{b}$ 和 $q$ 次询问，每次询问给出一个整数 $k_i$，你需要求出从初始状态开始，恰好经过 $k_i$ 秒后的分数。

输入格式

输入包含多组测试数据。输入的第一行包含一个整数 $T$（$1 \le T \le 10^3$），表示测试数据的组数。对于每组测试数据：

第一行包含三个整数 $a$，$b$ 和 $q$（$1 \le a, b \le 10^{12}$，$1 \le q \le 100$）。保证初始时 $\gcd(a, b) = 1$。

接下来的 $q$ 行中，第 $i$ 行包含一个整数 $k_i$（$1 \le k_i \le 10^{18}$），表示询问的时间。

输出格式

对于每次询问，输出一行，包含两个由空格隔开的整数 $a'$ 和 $b'$，分别表示从初始状态开始，恰好经过 $k_i$ 秒后的分数的分子和分母。

样例

输入样例 1

3
1 7 3
1
2
3
1 1 1
1
13 3 3
7
2
10

输出样例 1

1 4
2 5
1 2
1 1
5 4
8 3
8 7