Counting Triplets

kaidul DIU Team Practice Contest...
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.

Submit

Login to submit.

Contributors

Statistics

46% Solution Ratio
sahedsohelEarliest, Aug '17
ash_98Fastest, 2.2s
kazi_nayeemLightest, 393 kB
DIU_DauntlessShortest, 579B
Toph uses cookies. By continuing you agree to our Cookie Policy.