Sum of Even Fibonacci Numbers

Given an integer n, compute the sum of all even Fibonacci numbers that are less than or equal to n. The Fibonacci sequence is defined as follows: \(F_1 = 1, F_2 = 1\), and for \(n \ge 3\), \(F_n = F_{n-1} + F_{n-2}\). For example, if n is 10, the even Fibonacci numbers are 2 and 8, and their sum is 10. Your task is to implement a program that reads multiple test cases and, for each test case, outputs the required sum.

inputFormat

The first line of input contains an integer T representing the number of test cases. Each of the following T lines contains a single integer n (1 ≤ n ≤ 10⁶), which is the upper bound for the Fibonacci numbers to be considered.

outputFormat

For each test case, output a single line containing the sum of all even Fibonacci numbers that do not exceed n.

1
10

10