#P18012. Art of Multiplication

Art of Multiplication

Art of Multiplication

在 rr 进制下,整数 xx 的表示由 nn 个相同的数字 aa 组成,整数 yy 的表示由 mm 个相同的数字 bb 组成。

令 z=x⋅yz=x\cdot y。求 zz 的 rr 进制表示的各位数字之和,并将这个和也以 rr 进制输出。

输入格式

第一行一个整数 tt,表示测试用例数。接下来 tt 行,每行五个整数 n,m,a,b,rn,m,a,b,r。输入的这些参数均以通常的十进制表示。

输出格式

对每个测试用例输出一行,表示答案的 rr 进制形式,不含前导零。

数据范围

1≤t≤100001\le t\le10000,n,m≥1n,m\ge1,n+m≤1018n+m\le10^{18},1≤a,b<r≤101\le a,b<r\le10。

说明

例如 n=2,m=3,a=b=6,r=10n=2,m=3,a=b=6,r=10 时,66×666=4395666\times666=43956,其数位和为 2727。在二进制用例中,数位和也必须转成二进制输出。

样例 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

输出

27
84
204
100101
71