def solve():
n=int(input())
nums=list(map(int,input().split()))
ans = n * (n * 2 + 1)
visited = [0] * n
path = []
pt = 0
flag = False
while not visited[pt]:
path.append(pt)
visited[pt] = 1
pt += nums[pt]
if not 0 <= pt < n:
break
else:
ans -= (n - sum(visited)) * (2 * n + 1); flag = True
cnt = sum(visited)
if flag:
ans -= cnt * cnt
else:
ans -= (1 + cnt) * cnt // 2
new_visited = [0] * n
note = visited[:]
for i in range(n):
if not note[i]:
tmp = []
f = False
while not note[i]:
tmp.append(i)
note[i] = 1
i += nums[i]
if not 0 <= i < n: break
if (note[i] and new_visited[i] >= 0) or visited[i]: f = True
if f:
if new_visited[i]:
i = new_visited[i] - 1
for x in tmp:
new_visited[x] = i + 1
else:
for x in tmp:
new_visited[x] = -1
path_note = {v: i for i, v in enumerate(path)}
for i in range(n):
if not visited[i]:
if new_visited[i] != -1:
if visited[new_visited[i] - 1] == 0 or flag:
ans -= cnt
else:
ans -= cnt - path_note[new_visited[i] - 1]
print(ans)
for _ in range(int(input())):
solve()#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define sz(s) (int)s.size()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1e9 + 7;
const int N = 300300;
int n, a[N], col[N], cnt_col[N];
bool was[N], init_good;
ll ans;
bool used[N];
void f(int v) {
if (col[v] != -1)
return;
if (was[v]) {
col[v] = v;
return;
}
if (used[v]) {
col[v] = v;
return;
}
used[v] = 1;
int u = v + a[v];
if (u < 1 || u > n)
col[v] = 0;
else {
f(u);
col[v] = col[u];
}
}
void solve() {
ans = 0;
init_good = false;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
was[i] = 0;
{
int v = 1;
while (true) {
was[v] = 1;
v += a[v];
if (v < 1 || v > n) {
init_good = 1;
break;
}
if (was[v])
break;
}
}
for (int i = 1; i <= n; i++)
col[i] = -1, used[i] = 0;
for (int i = 1; i <= n; i++)
f(i);
for (int i = 0; i <= n; i++)
cnt_col[i] = 0;
for (int i = 1; i <= n; i++)
cnt_col[col[i]]++;
{
ll s = cnt_col[0];
if (init_good) {
for (int i = 1; i <= n; i++)
if (was[i])
s += cnt_col[i];
}
for (int i = 1; i <= n; i++)
was[i] = 0;
int v = 1;
while (true) {
if (init_good)
s -= cnt_col[v];
ans += s;
ans += n + 1;
was[v] = 1;
v += a[v];
if (v < 1 || v > n || was[v])
break;
}
for (int i = 1; i <= n; i++)
if (!was[i] && init_good)
ans += n + n + 1;
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) solve();
return 0;
}1384A - Common Prefixes | 371A - K-Periodic Array |
1542A - Odd Set | 1567B - MEXor Mixup |
669A - Little Artem and Presents | 691B - s-palindrome |
851A - Arpa and a research in Mexican wave | 811A - Vladik and Courtesy |
1006B - Polycarp's Practice | 1422A - Fence |
21D - Traveling Graph | 1559B - Mocha and Red and Blue |
1579C - Ticks | 268B - Buttons |
898A - Rounding | 1372B - Omkar and Last Class of Math |
1025D - Recovering BST | 439A - Devu the Singer and Churu the Joker |
1323A - Even Subset Sum Problem | 1095A - Repeating Cipher |
630F - Selection of Personnel | 630K - Indivisibility |
20B - Equation | 600B - Queries about less or equal elements |
1015A - Points in Segments | 1593B - Make it Divisible by 25 |
680C - Bear and Prime 100 | 1300A - Non-zero |
1475E - Advertising Agency | 1345B - Card Constructions |