#P9246. SPOJ GCDEX

    ID: 5366 传统题 1000ms 256MiB 尝试: 8 已通过: 5 难度: 5 上传者: 标签>CF1700普及+/提高-欧拉函数线性筛倍数枚举一维前缀和

SPOJ GCDEX

Description

给定正整数NN,求∑i=1n−1∑j=i+1ngcd(i,j)\sum_{i=1}^{n-1}\sum_{j=i+1}^ngcd(i,j)

Format

Input

T组数据,每行一个NN。(T≤106,N≤106)(T \leq 10^6,N \leq 10^6)

Output

每行一个答案。

Samples

3
10
100
200000
67
13015
143295493160