# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Counting Triplets

Given an array of **N** integers **A _{1}, A_{2}, A_{3} … A_{N}**. Vector has to find the number of Fibonacci Triplets in the array meaning how many triplets

**(i, j, k)**are there such that

**1 ≤ i < j < k ≤ N**and

**A**.

_{i}+ A_{j}= A_{k}For example, (2, 3, 5), (4, 9, 13) are Fibonacci Triplets but (2, 4, 5), (4, 3, 8) are not.

#### Input

First line of the input contains an integer **T** denoting the number of test cases. Next line contains an integer **N** denoting the size of the array. Following line contains **N** space separated integers **A _{1}, A_{2}, A_{3} … A_{N}**.

#### Constraints

**1 ≤ T ≤ 5**

**1 ≤ N ≤ 10**

^{5}**1 ≤ A**

_{i}< 2^{16}– 1#### Output

For each test case, print the number of ways to choose a Fibonacci Triplet from the array of **N** integers in a separate line.

#### Samples

Input | Output |
---|---|

1 6 2 3 3 4 7 11 | 3 |

#### Explanation

In above example, all 3 ways to choose a Fibonacci Triplet are -**(A**,

_{2}, A_{4}, A_{5})**(A**and

_{3}, A_{4}, A_{5})**(A**which are (3, 4, 7), (3, 4, 7) and (4, 7, 11) respectively.

_{4}, A_{5}, A_{6})*Note: The input files are large. Please use faster I/O.*

Login to submit

Login to unlock editorial