设 $x$ 是一个在 $r$ 进制下由 $n$ 个相同的数字 $a$ 组成的整数。同时，设 $y$ 是一个在 $r$ 进制下由 $m$ 个相同的数字 $b$ 组成的整数。

求数字 $z = x \cdot y$ 在 $r$ 进制下的数位之和，并以 $r$ 进制的形式输出该数位之和。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10\,000$)，表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例占一行，包含五个整数 $n, m, a, b, r$ ($n, m \ge 1, n + m \le 10^{18}$，$1 \le a, b < r \le 10$)。

输出格式

对于每个测试用例，在单独的一行中输出一个整数：表示以 $r$ 进制表示的该问题的答案。

样例

输入样例 1

5
2 3 6 6 10
6 11 7 7 10
20 25 2 6 10
13 37 1 1 2
57 1 4 2 8

输出样例 1

27
84
204
100101
71

说明

在第一个测试用例中，我们有 $x = 66_{10}$，$y = 666_{10}$，$z = 43\,956_{10}$。$z$ 的数位之和为 $27_{10}$。

在第四个测试用例中，二进制表示下 $z$ 的数位之和为 $37_{10} = 100101_2$。