Untitled

#include <iostream>
#include <vector>
#include <cstring>
#define MAX_N 200005
using namespace std;

int n;
int tree_num = 1;
int a[MAX_N];
int visited[MAX_N];
int dfs_tree[MAX_N];
int dfs_order[MAX_N];
bool tree_pass[MAX_N];

// build table
bool DFS(int id, int level) {
    if (id < 1 || id > n) return true;
    if (!visited[id]) {
        visited[id] = 1;
        dfs_tree[id] = tree_num;
    } 
    dfs_order[id] = level;
    int next = id + a[id];
    if (next < 1 || next > n) return DFS(next, level+1);
    if (!visited[next]) return DFS(next, level+1);
    else if (dfs_tree[id] != dfs_tree[next]) return tree_pass[next];
    else return false;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) { 
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }

        // DFS FOREST
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                bool find_the_exit = DFS(i, 1);
                if (find_the_exit) tree_pass[tree_num] = true;
                tree_num++;
            }
        }

        int ans = 0;
        for (int cur_id=1; cur_id<=n; cur_id++) {              // n
            
            // 現在在主幹上       
            if (dfs_tree[cur_id] == 1) {

                // n - (i-1) + i = n+1
                // 已經有 n+1 種找到出口的可能
                ans += (n+1);

                // 從範圍內找下一個位置
                for (int next_id=1; next_id<=n && next_id!=0 && next_id != cur_id; next_id++) { // 2n
                    
                    // 下一個也在主幹上
                    if (dfs_tree[next_id] == 1) {   

                        // 主幹沒終點 直接下一個
                        if (!tree_pass[1]) continue;
                        
                        // 主幹有終點
                        // check dfs_order
                        if (dfs_order[next_id] < dfs_order[cur_id]) continue; 
                        else ans++;
                    } 
                    
                    // 下一個不在主幹上 
                    else {

                        // 下一個的樹有終點
                        if (tree_pass[dfs_tree[next_id]]) ans++;

                        // 下一個的樹沒終點
                        else continue;
                    }
                }
            }

            // 現在不在主幹上
            else {

                // 假如主幹有終點，全部可能性都成立
                if (tree_pass[1]) {
                    
                    // 2n + 1 種
                    ans += (2*n+1);
                }
                    
                // 主幹沒終點
                else {

                    // 從範圍內找下一個位置
                    for (int next_id=1; next_id<=n && next_id!=0 && next_id != cur_id; next_id++) {
                    
                        // 下一個在主幹上
                        if (dfs_tree[next_id] == 1) {

                            // 因為主幹沒終點，continue
                            continue;
                        }

                        // 下一個也不在主幹上
                        else {

                            // 下一個的和現在的是同一棵樹
                            if (dfs_tree[next_id] == dfs_tree[cur_id]) {

                                // 這棵樹有終點 
                                if (tree_pass[dfs_tree[next_id]]) {
                                    
                                    // 有，比順序，下一個順序比現在小 => 不可能
                                    if (dfs_order[next_id] < dfs_order[cur_id]) continue;

                                    // 下一個順序比現在大，答案 +1
                                    else ans++;   
                                }
                                
                                // 這棵樹沒有終點 => 不可能
                                else continue;
                            }

                            // 不是
                            else {
                            
                                // 下一個的樹是否有終點
                                if (tree_pass[dfs_tree[next_id]]) {

                                    // 有，答案 +1
                                    ans++;
                                }

                                // 沒有 => 不可能 
                                else continue;
                            }
                        }
                    }
                }
            }
            
        }

        cout << ans << '\n';

        tree_num = 1;
        memset(a, 0, sizeof(a));
        memset(visited, 0, sizeof(visited));        
        memset(dfs_order, 0, sizeof(dfs_order));
        memset(dfs_tree, 0, sizeof(dfs_tree));
        memset(tree_pass, 0, sizeof(tree_pass));
    }

    return 0;
}