Description

给定正整数$N$，求$\sum_{i=1}^{n-1}\sum_{j=i+1}^ngcd(i,j)$

Format

Input

T组数据，每行一个$N$。$(T \leq 10^6,N \leq 10^6)$

Output

每行一个答案。

Samples

3
10
100
200000

67
13015
143295493160