题目描述

给定 $n$，求 $\sum\limits_{i=1}^n\sum\limits_{j=1}^n\varphi(\gcd(i,j))$。

输入格式

第一行为一个正整数 $T$，表示数据组数。

接下来 $T$ 行为询问，每行包含一个正整数 $n$。

输出格式

按读入顺序输出答案。

1
10

136

数据范围与约定

对于 $100\%$ 的数据，$T\le 5\times 10^3$，$n\le 10^7$。

题目来源

By FancyCoder