#P1431. 法雷数列(二)

法雷数列(二)

对任意给定的一个自然数n,将分母小于等于n的不可约的真分数按升序排列,并且在第一个分数之前加上0/1,在最后一个分数之后加上1/1,这个序列称为n级法雷数列,以Fn表示。如F5为:0/1,1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5,1/1.其元素个数为11.

现在给出n让你求其n级法雷数列中元素的个数。

Input

有多组测试数据组数小于1500001,
每组测试数据有一个整数n(0<n<=1500000).

Output

n级法雷数列中元素的个数

Sample Input

1
2
5

Sample Output

2
3
11

HINT

Source