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