Infinite Path cf-1327D

//cyclic permutation
//tutorial - https://www.youtube.com/watch?v=rwAqAmljjxU
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 100;

vector<int> all_col;
int p[N], c[N];
int vis[N];

void dfs(int u, int d) {
    all_col.push_back(c[u]);
    vis[u] = 1;
    if(vis[p[u]] == 0) dfs(p[u], d+1);
}


int main() {
    // freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);

    int tc;
    cin >> tc;
    while(tc--) {
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> p[i];
        for(int i = 1; i <= n; i++) cin >> c[i];
        for(int i = 1; i <= n; i++) vis[i] = 0;
        int ans = 1e9;
        for(int i = 1; i <= n; i++) {
            if(vis[i] == 0) {
                dfs(i, 0);
                int cyc_len = (int)all_col.size();
                ans = min(ans, cyc_len);
                for(int k = 1; k <= cyc_len; k++) {
                    if(cyc_len%k != 0) continue;
                    for(int i = 0; i < k; i++) {
                        bool found = true;
                        for(int j = i; j < cyc_len; j += k) {
                            if(all_col[i] != all_col[j]) {
                                found = false;
                                break;
                            }
                        }
                        if(found) ans = min(ans, k);
                    }
                }
                all_col.clear();
            }
        }
        cout << ans << endl;
    }

    return 0;
}