×

计蒜客

  1. 题库
  2. Sum
  3. 问答
  • 27.3%
  • 1000ms
  • 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

题目来源

ACM-ICPC 2018 南京赛区网络预赛

想挑战这道题吗

  • main.c