Problem F: Farey Sequence

slipは数字を眺めるのが好きである。 ファイルをダウンロードしているときの、残り時間を眺めているだけで、時間を潰せるほどである。 そんなslipが友人から面白い数列を教えられた。 その数列の定義は以下のとおりである。

一般項をF_nと表わす。 F_nとは、n以下の分母を持つ0以上1以下のすべての約分された分数(既約分数)を小さな順から並べたものである。 ただし、整数0、1はそれぞれ分数0/1、1/1として扱われる。

つまりF₃は、

F3 = (0/1, 1/3, 1/2, 2/3, 1/1)

のように表される。

F₅であれば

F5 = (0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1)

と表される。

slipはこの数列にすぐにのめり込んだ。 しかしこの数列を眺めていても、なかなか特徴がつかめなかった。 特徴をつかむためにまずは各項の項数がいくつあるのか調べようと思ったが、 増え方の規則がわからず、自力で理解することを断念した。

そこで、 勝手に友人と思っているあなたに、指定した項にどれだけの項数があるのかを聞くことにした。 あなたの仕事は、与えられた項における項数を求めることである。

Input

入力は以下の形式で与えられる。

t
n1
...
ni
...
nt

t(1 ≤ t ≤ 10000)はテストケースの数である。 n_i(1 ≤ n_i ≤ 1000000)は与えられた項の番号である。

Output

各テストケースごとに、項数を1行に表示せよ。

Sample Input

2
3
5

Output for Sample Input

5
11

Note

Commentary

 

---