Given some sticks with length equal to a Fibonacci number, for example 2, 3, 5, 8, etc. You have to make triangle with positive area using these sticks. One stick can be used at most once (for making only one triangle). N-th Fibonacci number is F(N). F (1) = 2 F (2) = 3 F (n) = F (n − 1) + F (n − 2) for n ≥ 3 Input Given T ≤ 100 denoting test cases. Each case starts with a positive integer n ≤ 1000. Then, there will be n non-negative integers, i-th integer denote the number of sticks with side length F(i). Output For each case you have to print an integer in a line denoting the maximum number of triangles (with positive area) you can form using these sticks. The number is guaranteed to be less than 108. Sample Input 3 3 162 3 262 3 171 Sample Output 3 3 3