问题描述

定义函数 \(F(N,M)\):

\[F(N, M) = \sum_{i=1}^{N} \sum_{j=1}^{M} S(i^2) \times S(j^2) \times S(i \times j)\]

其中 \(S(n)\) 为 \(n\) 的约数个数.

请你对于给定的 \(N, M\), 快速求出 \(F(N, M)\) 对 \(1073741824\) 取模后的值.

输入格式

由于某些原因, 本题每个测试点包含多组数据.

第一行一个整数 \(q\).

接下来 \(q\) 行,每行两个整数 \(N, M\),表示询问 \(F(N,M)\) 的值.

输出格式

输出共 \(q\) 行, 依次为每个询问的结果对 \(1073741824\) 取模后的值.

样例输入

3
10 11
866 845
198557 179743

样例输出

18806
652720324
392727641

数据范围

对于前 \(10\%\) 的数据, \(q = 10, N,M \leq 100\);

对于前 \(20\%\) 的数据, \(q = 10, N,M \leq 1000\);

对于前 \(40\%\) 的数据, \(q \leq 20, N,M \leq 200000\);

对于前 \(50\%\) 的数据, \(q \leq 1250, N,M \leq 200000\);

对于另外 \(10\%\) 的数据, \(q = 9998, N,M \leq 200000\), 保证 \(N = M\);

对于另外 \(10\%\) 的数据, \(q = 9999, N,M \leq 200000\), 保证所有的 \(M\) 相等;

对于所有数据, \(q \leq 10000, N,M \leq 200000\).

时间限制 \(\text{2s}\), 空间限制 \(\text{512MB}\).

请注意常数优化, 避免失分.

提示

对于一个整数 \(x\), 如果有 \(x = A \times B\), 则对于 \(x\) 的任意一个因子 \(d\), 一定存在 \(i|A, j|B\), 使得 \(i \times j = d\).