题目描述

有一张 n*m 的数表，其第 i 行第 j 列（$1 \leqslant i \leqslant n, 1 \leqslant j \leqslant m$）的数值为能同时整除 i 和 j 的所有自然数之和。

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

输入格式

输入包含多组数据。

输入的第一行一个整数Q表示测试点内的数据组数.

接下来Q行，每行三个整数$n，m，a$描述一组数据。

输出格式

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

样例

2
4 4 3
10 10 5

20
148

数据范围

对于所有数据，$1 \le Q \le 2*10^4,1 \le n,m \le 10^5,|a| \le 10^9$

来源

• sdoi2014
• bzoj3529
• 信息学奥赛之数学一本通
• stong9070整理