[SDOI2014]数表

题目描述

有一张N\*m的数表,其第i行第j列(1 < =i < =n,1 < =j < =m)的数值为能同时整除i和j的所有自然数之和。给定a,计算数表中不大于a的数之和。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

2
4 4 3
10 10 5

输出样例 #1

20
    148

说明

1 < =N.m < =10^5 , 1 < =Q < =2\*10^4