#2193. 「SDOI2014」数表

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

有一张 n \times m 的数表,其第 i 行第 j 列( 1 \leq i \leq n, 1 \leq j \leq m )的数值为能同时整除 i j 的所有自然数之和。

给定 a ,计算数表中不大于 a 的数之和。

输入格式

输入包含多组数据。
输入的第一行一个整数 Q 表示测试点内的数据组数。
接下来 Q 行,每行三个整数 n, m, a 描述一组数据。

输出格式

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

样例

样例输入

2
4 4 3
10 10 5

样例输出

20
148

数据范围与提示

对于所有数据, 1 \leq Q \leq 2 \times 10^4,\ 1 \leq n,m \leq 10^5,\ a \leq 10^9