sums

时限 1.5s - 空限 512MB

输入文件 sums.in - 输出文件 sums.out - 提交程序 sums.cpp

题目描述

给定 $A,B,C$ ($1\le A,B,C\le 10^4$), 求:

$$\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C[i|j|k]\varphi(ijk)$$

其中 $[i|j|k]$ 为 $1$ 当且仅当 $i$ 整除 $j$ 并且 $j$ 整除 $k$, 否则为 $0$, 和 $\varphi(ijk)$ 为小于等于 $ijk$ 且与 $ijk$ 互质的正整数个数.

小 D 有 $T$ 组询问 ($1\le T\le 5\times 10^5$).

输入格式

第一行一个正整数 $T$ ($1\le T\le 5\times 10^5$), 为询问个数。

接下来 $T$ 行, 每行三个正整数 $A,B,C$ ($1\le A,B,C\le 10^4$), 对应一个询问。

输出格式

输出 $T$ 行. 对于每一行, 输出一个非负整数, 为对应组询问的答案。

输入输出样例

样例 1

输入

3
3 5 6
20 20 50
31 41 59

输出

134
180070
743368

评分规定

对于 $20\%$ 的数据, $T,A,B,C\le 100$.
对于另外 $20\%$ 的数据, $T=1$.
对于 $60\%$ 的数据, $T\le 10^3$.
对于 $100\%$ 的数据, $1\le A,B,C\le 10^4$ 并且 $1\le T\le 5\times 10^5$.