数表

Description

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

Input

　　输入包含多组数据。

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

　　接下来Q行，每行三个整数n,m,a(|a|<=10^9 )描述一组数据。

Output

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

Sample Input

2

4 4 3

10 10 5

Sample Output

20

148

Hint

不妨设\(n<m\)。

同时整除\(i,j\)的自然数之和就是\(gcd(i,j)\)的约数之和。我们设\(f(i)=\sum_{d|i}d\)。

则:

\[ \displaystyle ans=\sum_{g=1}^{n}f(g)\sum_{i=1}^{\lfloor \frac{n}{g} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{g} \rfloor}[gcd(i,j)=1]\\ =\sum_{g=1}^{n}f(g)\sum_{i=1}^{\lfloor \frac{n}{g} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{g} \rfloor}\sum_{d|i,d|j}\mu(d) \]

又来套路一波：设\(T=gd\)，\(\displaystyle ans=\sum_{T=1}^{n}\sum_{d|T}\mu(d)f(\frac{n}{d})\lfloor \frac{n}{T} \rfloor\lfloor \frac{m}{T} \rfloor\)。

然后又了a的限制后，我们就将询问和\(f\)都离线下来排序，加入树状数组里面。

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include