Fe3b0onacci Pairs

Input

The first line contains a single integer $t$ $(1 \leq t \leq 1 0^{4}$ (1 \le t \le 10^4) — the number of test cases.

The first line of each test case contains a single integer $n$ $(2 \leq n \leq 2 \cdot 1 0^{5})$ (2 \le n \le 2 \cdot 10^5).

The second line of each test case contains $n$ integers $a_{1}, a_{2}, ... a_{n}$ a_1 , a_2 , ... a_n $(0 \leq a_{i} \leq 1 0^{9})$ (0 \le a_i \le 10^9).

It's guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Output

For each test case, print a single integer — the count of fe3b0onacci pairs.

Examples

Example 1

Loading

Note

In the first test case, Fe3b0onacci pairs are:

$i = 1, j = 2$ i = 1 , j = 2 , $Fib (0 + 1) = Fib (0) + Fib (1) = 0 + 1 = 1$ \mathsf{Fib}(0 + 1) = \mathsf{Fib}(0) + \mathsf{Fib}(1) = 0 + 1 = 1.

$i = 1, j = 3$ i = 1 , j = 3 , $Fib (0 + 2) = Fib (0) + Fib (2) = 0 + 1 = 1$ \mathsf{Fib}(0 + 2) = \mathsf{Fib}(0) + \mathsf{Fib}(2) = 0 + 1 = 1.

$i = 2, j = 3$ i = 2 , j = 3 , $Fib (1 + 2) = Fib (1) + Fib (2) = 1 + 1 = 2$ \mathsf{Fib}(1 + 2) = \mathsf{Fib}(1) + \mathsf{Fib}(2) = 1 + 1 = 2.

Scoring

Subtask $1$ ( $150$ points): No additional constraints.