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

Limits: 12s, 1.0 GB

Given an array of N integers A1, A2, A3 … AN. 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 Ai + Aj = Ak.

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 A1, A2, A3 … AN.

Constraints

1 ≤ T ≤ 5
1 ≤ N ≤ 105
1 ≤ Ai < 216 – 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

InputOutput
1
6
2 3 3 4 7 11
3

Explanation

In above example, all 3 ways to choose a Fibonacci Triplet are - (A2, A4, A5), (A3, A4, A5) and (A4, A5, A6) which are (3, 4, 7), (3, 4, 7) and (4, 7, 11) respectively.

Note: The input files are large. Please use faster I/O.
Discussion
Submit

Login to submit

Editorial

Login to unlock editorial