×

# 计蒜客

1. 题库
2. Sum
3. 问答
• 28%
• 512000K

A square-free integer is an integer which is indivisible by any square number except $1$. For example, $6 = 2 \cdot 3$ is square-free, but $12 = 2^2 \cdot 3$ is not, because $2^2$ is a square number. Some integers could be decomposed into product of two square-free integers, there may be more than one decomposition ways. For example, $6 = 1\cdot 6=6 \cdot 1=2\cdot 3=3\cdot 2, n=ab$ and $n=ba$ are considered different if $a \not = b$. $f(n)$ is the number of decomposition ways that $n=ab$ such that $a$ and $b$ are square-free integers. The problem is calculating $\sum_{i = 1}^nf(i)$.

### Input

The first line contains an integer $T(T\le 20)$, denoting the number of test cases.

For each test case, there first line has a integer $n(n \le 2\cdot 10^7)$.

### Output

For each test case, print the answer $\sum_{i = 1}^n f(i)$.

### Hint

$\sum_{i = 1}^8 f(i)=f(1)+ \cdots +f(8)$
$=1+2+2+1+2+4+2+0=14$.

#### 样例输入

2
5
8

#### 样例输出

8
14

• main.c