for _ in range(int(input())):
    n = int(input())
    p = [int(x) - 1 for x in input().split()]
    ans = 3
    for i in range(n):
        if p[p[i]] == i:
            ans = 2
    print(ans)

fun main() {
    repeat(readln().toInt()) {
        val s = readln().map { it.code - '0'.code }
        val zeroes = s.count { it == 0 }
        val cnt = intArrayOf(0, 0)
        var ans = 0L
        for (c in s) {
            cnt[c]++
            if (c == 0)
                ans += if (cnt[1] > 0) 1 else 0
            else
                ans += (zeroes - cnt[0])
        }
        println(ans)
    }
}

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

using li = long long;
const li INF = 1e18;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<li> a(n);
    for (auto& x : a) cin >> x;
    vector<vector<li>> dp(n + 1, vector<li>(k + 1, INF));
    dp[0][0] = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j <= k; ++j) {
        li mn = INF;
        for (int d = 0; j + d <= k && i + d < n; ++d) {
          mn = min(mn, a[i + d]);
          dp[i + d + 1][j + d] = min(dp[i + d + 1][j + d], dp[i][j] + (d + 1) * mn);
        }
      }
    }
    cout << *min_element(dp[n].begin(), dp[n].end()) << '\n';
  }
}

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

#define sz(a) int((a).size())
using li = long long;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) {
      return b[i] > b[j];
    });
    li f = 0, p = 0;
    for (int i : ord) p += max(0, b[i] - a[i]);
    li ans = 0;
    multiset<int> s;
    if (sz(s) == k) ans = max(ans, p - f);
    for (int i : ord) {
      p -= max(0, b[i] - a[i]);
      s.insert(a[i]);
      f += a[i];
      if (sz(s) > k) {
        f -= *s.rbegin();
        s.erase(--s.end());
      }
      if (sz(s) == k) ans = max(ans, p - f);
    }
    cout << ans << '\n';
  }
}

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

#define sz(a) int((a).size())

vector<int> t, p;

void push(int v) {
  if (v * 2 + 2 >= sz(t)) return;
  t[v * 2 + 1] += p[v]; p[v * 2 + 1] += p[v];
  t[v * 2 + 2] += p[v]; p[v * 2 + 2] += p[v];
  p[v] = 0;
}

void upd(int v, int l, int r, int L, int R, int x) {
  if (L >= R) return;
  if (l == L && r == R) {
    t[v] += x; p[v] += x;
    return;
  }
  int m = (l + r) / 2;
  push(v);
  upd(v * 2 + 1, l, m, l, min(m, R), x);
  upd(v * 2 + 2, m, r, max(m, L), R, x);
  t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
}

int get(int v, int l, int r, int L, int R) {
  if (L >= R) return 1e9;
  if (l == L && r == R) return t[v];
  int m = (l + r) / 2;
  push(v);
  return min(
    get(v * 2 + 1, l, m, l, min(m, R)),
    get(v * 2 + 2, m, r, max(m, L), R)
  );
}

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto& x : a) cin >> x, --x;
  t = p = vector<int>(4 * n);
  vector<vector<int>> pos(n);
  int ans = 0, st = 0;
  for (int i = 0; i < n; ++i) {
    int x = a[i];
    pos[x].push_back(i);
    int k = sz(pos[x]);
    if (k > 0) upd(0, 0, n, st, pos[x][k - 1] + 1, +1);
    if (k > 1) upd(0, 0, n, st, pos[x][k - 2] + 1, -2);
    if (k > 2) upd(0, 0, n, st, pos[x][k - 3] + 1, +1);
    if (get(0, 0, n, st, i + 1) == 0) {
      ans += 1;
      st = i + 1;
    }
  }
  cout << ans << '\n';
}

int main() {
  int t;
  cin >> t;
  while (t--) solve();
}

#include<bits/stdc++.h>

using namespace std;

mt19937_64 rnd(12341234);

int n, k;
vector<int> deck;
vector<int> dp;
vector<vector<bool>> odd;
vector<bool> full_odd;
vector<long long> val;
vector<long long> hs;      

bool bad(const vector<bool>& v)
{
    for(int i = 0; i < k; i++)
        if(!v[i])
            return false;
    return true;
}

vector<bool> inv(const vector<bool>& v)
{
    vector<bool> res(k);
    for(int i = 0; i < k; i++)
        res[i] = !v[i];
    return res;
}

vector<bool> get_suffix(int l)
{
    vector<bool> v(k);                     
    for(int i = l; i < n; i++) v[deck[i]] = !v[deck[i]];
    return v;
}

int get_next(long long cur, int x)
{
    for(int i = x; i <= n; i += 2)
        if(hs[i] == cur)
            return i;
    return -1;
}                

int main()
{
    cin >> n >> k;
    deck.resize(n);
    for(int i = 0; i < n; i++) cin >> deck[i];
    for(int i = 0; i < n; i++) --deck[i];
    val.resize(k);
    for(int i = 0; i < k; i++)
        while(val[i] == 0)
            val[i] = rnd();

    int max_score = 0;
    dp.resize(n + 1);
    full_odd.resize(k);
    odd.resize(n + 1, vector<bool>(k));
    hs.resize(n + 1);
    long long cur_hash = 0;
    for(int i = 0; i < n; i++)
    {
        cur_hash ^= val[deck[i]];
        if(full_odd[deck[i]]) max_score++;
        full_odd[deck[i]] = !full_odd[deck[i]];
        odd[i + 1] = full_odd;
        hs[i + 1] = cur_hash;
    }   

    for(int i = k; i <= n; i++)
        dp[i] = 1e9;                          
    long long start = 0ll;
    for(int i = 0; i < k; i++) start ^= val[i];
    int pos = get_next(start, k);
    if(pos == -1)
    {
        cout << max_score << endl;  
    }
    else
    {
        dp[pos] = 0;
        int ans = 1e9;
        for(int p = k; p <= n; p += 2)
        {
            if(dp[p] > 1e8) continue;   
            vector<bool> suff = get_suffix(p);
            vector<int> o, e;
            for(int j = 0; j < k; j++)
                if(suff[j])
                    e.push_back(j);
                else
                    o.push_back(j);
            int es = e.size();
            int os = o.size();
            bool flag = true;
            for(int i = 0; i < os && flag; i++)
                for(int j = 0; j < i && flag; j++)
                {
                    int x = o[i];
                    int y = o[j];
                    int add = 0;         
                    long long h = hs[p] ^ val[x] ^ val[y];
                    int pos = get_next(h, p);
                    if(pos == -1)                  
                    {
                        flag = false;
                        ans = min(ans, dp[p] + add);
                    }
                    else
                        dp[pos] = min(dp[pos], dp[p] + add);
                }

            for(int i = 0; i < os && flag; i++)
                for(int j = 0; j < es && flag; j++)
                {
                    int x = o[i];
                    int y = e[j];
                    int add = 1;         
                    long long h = hs[p] ^ val[x] ^ val[y];
                    int pos = get_next(h, p);    
                    if(pos == -1)
                    {
                        flag = false;
                        ans = min(ans, dp[p] + add);
                    }
                    else
                        dp[pos] = min(dp[pos], dp[p] + add);
                }

            for(int i = 0; i < es && flag; i++)
                for(int j = 0; j < i && flag; j++)
                {
                    int x = e[i];
                    int y = e[j];
                    int add = 2;                             
                    long long h = hs[p] ^ val[x] ^ val[y];
                    int pos = get_next(h, p);
                    if(pos == -1)
                    {
                        flag = false;
                        ans = min(ans, dp[p] + add);
                    }
                    else
                        dp[pos] = min(dp[pos], dp[p] + add);
                }
        }
        cout << max_score - ans << endl;
    }       
}