Binary Sequence of Prime Number is a binary sequence that created by converting prime number to base-2 (without leading zeros):

• (2)₁₀=(10)₂
• (3)₁₀=(11)₂
• (5)₁₀=(101)₂
• (7)₁₀=(111)₂
• ...

If all base-2 of prime number joined, then we get the binary sequence like this: 10111011111011110110...

Now your task is to count how many digit '1' appear in the first N terms of the sequence, example:

• If N=3, digit '1' appear 2 times: 101110...
• If N=10, digit '1' appear 8 times: 1011101111101...

Input

The first line is an integer T (1 ≤ T ≤ 50,000), denoting the number of test cases. Then, T test cases follow.

For each test case, there is an integer N (0 ≤ N ≤ 150,000,000) written in one line.

Output

For each test case, output the number of digit '1' appear in the first N terms of the sequence

Example

Input:
3
3
10
50

Output:
2
8
36

See also: Another problem added by Tjandra Satria Gunawan