「BZOJ3529」[SDOI2014]数表

Description

有一张 n×mn\times m 的数表,其第 ii 行第 jj(1in,1jm)(1 \leq i \leq n, 1 \leq j \leq m)的数值为
能同时整除 iijj 的所有自然数之和。
给定 aa , 计算数表中不大于 a 的数之和。

Input

输入包含多组数据。
输入的第一行一个整数Q表示测试点内的数据组数
接下来QQ行,每行三个整数nnmma(a109)a(|a| \leq 10^9)描述一组数据。
1N1 \leq Nm105m \leq 10^51Q2×1041 \leq Q \leq 2\times 10^4

Output

对每组数据,输出一行一个整数,表示答案模2312^{31}的值。

Sample Input

1
2
3
2
4 4 3
10 10 5

Sample Output

1
2
20
148

Solution