#include <bits/stdc++.h>
using namespace std;

struct Dsu {
    vector<int> pa, rk;
    Dsu(int n) : pa(n), rk(n) {
        iota(pa.begin(), pa.end(), 0);
    }
    int anc(int x) {
        return pa[x] == x ? x : pa[x]=anc(pa[x]);
    }
    bool join(int x, int y) {
        x = anc(x);
        y = anc(y);
        if (x == y) return false;
        if (rk[x] < rk[y]) swap(x, y);
        pa[y] = x;
        if (rk[x] == rk[y]) ++rk[x];
        return true;
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int t; cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> p(n), q(n);

        for (int i = 0; i < n; i++) {
            cin >> p[i];
            --p[i];
            q[p[i]] = i;
        }

        vector<vector<pair<int,int>>> e(n + 1);
        const int K = ceil(sqrt(n));
        for (int i = 0; i < n; i++) {
            for (int j = max(0, i-K); j <= min(n-1, i+K); j++) {
                if (j == i) continue;
                int64_t cost = 1LL * abs(i - j) * abs(p[i] - p[j]);
                if (cost <= n) {
                    e[cost].emplace_back(i, j);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = max(0, i-K); j <= min(n-1, i+K); j++) {
                if (j == i) continue;
                int64_t cost = 1LL * abs(i - j) * abs(q[i] - q[j]);
                if (cost <= n) {
                    e[cost].emplace_back(q[i], q[j]);
                }
            }
        }

        Dsu dsu(n);
        int64_t ans = 0;
        for (int i = 1; i <= n; i++) {
            for (auto [a, b]: e[i]) {
                if (dsu.join(a, b)) {
                    ans += i;
                }
            }
        }

        cout << ans << '\n';
    }
    return 0;
}