B. Another Problem about Beautiful Pairs
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the array $$$a$$$, we call a pair of indices $$$i$$$, $$$j$$$ beautiful if the following condition holds:

  • $$$a_{i} \cdot a_{j} = j - i$$$.

Count the number of beautiful pairs in the array $$$a$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

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

The second line of each test case contains $$$n$$$ integers $$$a_{i}$$$ ($$$1 \le a_{i} \le 10^{9}$$$).

Additional constraints on the input:

  • The sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.
Output

For each test case, output a single integer — the answer to the problem.

Example
Input
4
5
1 1 2 100 4
6
2 2 1 1 2 2
10
1 1 2 3 4 1 1 7 3 9
2
1000000000 1000000000
Output
3
7
10
0
Note

In the first example, there are $$$3$$$ beautiful pairs: ($$$1, 2$$$), ($$$1, 3$$$), and ($$$1, 5$$$).

In the second example, there are $$$7$$$ beautiful pairs: ($$$1, 3$$$), ($$$1, 5$$$), ($$$2, 4$$$), ($$$2, 6$$$), ($$$3, 4$$$), ($$$3, 5$$$), and ($$$4, 6$$$).