The Fibonacci Sequence is the series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... The next number is found by adding up the two numbers before it. The 2 is found by adding the two numbers before it (1+1). One such Fibonacci series is 1,2,3,5,8,13,21,34,55,89... By considering the numbers in the above (starting with 1 & 2) Fibonacci series whose values do not exceed N, find the sum of the even-valued terms.

Input Format First line contains T that denotes the number of test cases. This is followed by T lines, each containing an integer, N.

Output Format Print the required answer for each test case.

Constraints

1≤T≤10^5
10≤N≤4×10^16

Sample Input

3
6
5
9

Sample Output

2
2
10