#include <bits/stdc++.h>
using namespace std;
// #define LOCAL
// Part I
/*
hi,hj,hk
WLOG i < j < k
Case work on which hi/hj/hk has largest value k-i
Case 1: h[i] = k-i
*) Fixing i, fixes k
-> k = i+h[i]
*) Then
hk = k-j or hk = j-i
-> In both cases: j is fixed, 2*N possible triples
Case 2: h[k] = k-i
*) Fixing k, fixes i
-> i = k-h[k]
*) Now,
h[i] = j-i or h[i] = k-j
-> In both cases: j fixed, 2*N possible triples
Case 3: h[j] = k-i
*) If h[i] = j-i
-> Fixing i, fixes j (h[i]+i = j)
-> Then k = h[j]+i = k
*) h[i] = k-j
h[j] = k-i
h[k] = j-i
--> h[j]-h[i] = k-i-(k-j) = j-i
--> h[j]-j = h[i]-i = c
--> h[k] - h[j] = j - k
h[k] + k = h[j] + j
2D points/lines
h[i] - i = 0
[-N, N] -> [0,2*N]
(i,h[i])
(j,h[j])
(k,h[k])
Equations:
i) h[j] + j = h[k] + k
ii) h[j]-j = h[i] - i
For equation ii) --> O(n^2) solution
-> If diagonal has size <= sqrt(n), then O(n) possible
->
h[k]+k = h[j]+j = diag+j+j
*/
constexpr long long MUL = 200'001;
constexpr long long MULSQ = MUL * MUL;
long long chash(int i, int j, int k) {
array<int,3> a{i,j,k};
sort(a.begin(), a.end());
long long h = a[0];
h += MUL * a[1];
h += MULSQ * a[2];
return h;
}
bool check(int i, int j, int k, vector<int>& h) {
if (min(i,min(j,k)) < 0 || max(i,max(j,k)) >= h.size()) {
return false;
}
array<int,3> a{abs(j-i), abs(k-i), abs(k-j)};
array<int,3> b{h[i],h[j],h[k]};
sort(a.begin(), a.end());
sort(b.begin(), b.end());
return a==b;
}
int count_triples(vector <int32_t> a){
int n = a.size();
int ans = 0;
for (int i = 0; i < n; i++){
if (i + a[i] < n){
int j = i + a[i];
if (a[j] < a[i]){
int k = j - a[j];
if (a[k] + a[j] == a[i]){
ans++;
}
if (2 * a[j] != a[i]){
k = i + a[j];
if (a[k] + a[j] == a[i]){
ans++;
}
}
}
}
if (i - a[i] >= 0){
int j = i - a[i];
if (a[j] < a[i]){
int k = j + a[j];
if (a[k] + a[j] == a[i]){
ans++;
}
if (2 * a[j] != a[i]){
k = i - a[j];
if (a[k] + a[j] == a[i]){
ans++;
}
}
}
}
}
vector <int> b[2 * n + 1];
for (int i = 0; i < n; i++){
b[a[i] - i + n].push_back(i);
}
int cutoff = sqrt(n);
for (int x = 1; x <= 2 * n; x++){
if (b[x].size() <= cutoff){
for (int v1 = 0; v1 < b[x].size(); v1++){
int i = b[x][v1];
for (int v2 = 0; v2 < v1; v2++){
int j = b[x][v2];
int k = j + a[i];
if (k < n && k > i){
if (a[i] == (k - j) && a[j] == (k - i) && a[k] == (i - j)){
ans++;
}
}
}
}
} else {
for (int k = 0; k < n; k++){
int C = x - n;
int sum = k - C;
int diff = a[k];
if (diff % 2 == sum % 2){
int i = (sum - diff) / 2;
int j = (sum + diff) / 2;
if (0 <= i && i < n && 0 <= j && j < n && a[i] - i == C && a[j] - j == C){
ans++;
}
}
}
}
}
for (int i = 0; i < n; i++){
int j = i + a[i];
if (j < n && a[j] > a[i]){
int k = i + a[j];
if (k < n){
if (a[k] + a[i] == a[j] && a[k] != a[i]){
ans++;
}
}
}
}
return ans;
}
std::vector<int> construct_range(int M, int K) {
M = 0;
K = 0;
return {M,K};
}
#ifdef LOCAL
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tc;
cin >> tc;
while (tc--) {
int n;
cin >> n;
vector<int> a(n);
for (auto& e : a) cin >> e;
cout << count_triples(a) << '\n';
}
return 0;
}
#endif
