“跳找”搜索引擎的开发过程涉及到大量数据包的传输，为了保证传输过程稳定，你选择了用下面的方式算出一个校验码：

定义函数 $q(n,c)$ ，满足下列性质：

• 对所有质数 $p$ 和非负整数 $k$，有 $q(p^k,c)=p^{c\lfloor k/2\rfloor }$；

• 对所有互质的正整数 $n,m$ 有 $q(nm,c)=q(n,c)q(m,c)$。（即在第一维上满足积性）

不难发现，当 $c$ 确定后，可以根据上述性质唯一确定每个 $q(n,c)$ 的值。

我们可以把数据包认为是由若干个非负整数对 $(u_i,v_i)$ 组成的序列。这样我们先通过上面的算法计算出 $q(u_i\cdot v_i,c)$ 作为该整数对的校验码，然后将所有整数对的校验码求和再对 $2^{32}$ 取余后，就可以得到数据包的校验和。

现在你有一个非常大的数据包，其大小为 $n\times m$，且对于所有满足 $1\le i\le n,1\le j\le m$ 的 $(i,j)$，数据包中包含恰好一个整数对 $(i,j)$。请你计算出该数据包的校验和。

也就是说，对于给定的正整数 $n,m,c$，你需要求出下列式子对 $2^{32}$ 取模的值：

$$\sum _{i=1}^n\sum _{j=1}^{m}q(ij,c).$$

输入格式

本题有多组测试数据。

第一行一个正整数 $T$，表示数据组数。

下面 $T$ 行，每行三个整数 : $n,m,c$，意义如题目所述。

输出格式

对于每组测试数据，输出一行一个整数，表示答案对 $2^{32}$ 取模的结果。

样例一

input

3
10 100 1
998 244 353
1911 1949 1978

output

3733
3704996707
981669122

样例二

input

3
1 9078917 1
1 99989717 22
92734 3529465017 68715

output

49378630
1117102208
1722526387

限制与约定

对于所有数据, $1\le n\le 5\times {10}^5,1\le m\le 1.2\times {10}^{11},1\le c\le {10}^5,1\le T\le 3$。

时间限制：$5\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载