[SDOI2014]数表

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

2
4 4 3
10 10 5

输出样例 #1

20
148

说明

$1\le n,m\le 10^5$,$1\le Q\le 2\times 10^4$。