Counting Triplets

Limits 10s, 1.0 GB

Given an array of NN integers A1A_1, A2A_2, A3A_3, …, ANA_N. Vector has to find the number of Fibonacci Triplets in the array meaning how many triplets (i,j,k)(i, j, k) are there such that 1i<j<kN1 ≤ i < j < k ≤ N and AiA_i + AjA_j = AkA_k.

For example, (2,3,5)(2, 3, 5), (4,9,13)(4, 9, 13) are Fibonacci Triplets but (2,4,5)(2, 4, 5), (4,3,8)(4, 3, 8) are not.

Input

First line of the input contains an integer TT (1T51 ≤ T ≤ 5) denoting the number of test cases. Next line contains an integer NN (1N1051 ≤ N ≤ 10^5) denoting the size of the array. Following line contains N space separated integers A1A_1, A2A_2, A3A_3, …, ANA_N (1Ai<21611 ≤ A_i < 2^{16} – 1).

Output

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

Sample

InputOutput
1
6
2 3 3 4 7 11
3

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


The input files are large. Please use faster I/O.