#include <bits/stdc++.h>
#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
using namespace std;
template<typename U, typename V> bool maxi(U &a, V b) {
if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
if (a > b or a == -1) { a = b; return 1; } return 0;
}
const int N = (int)1e5 + 9;
const int mod = (int)1e9 + 7;
int n, m;
int mx[N], a[5][N], L[N], R[N];
vector<int> g[N];
void dfs(int u, int p) {
mx[u] = R[u];
for(int v : g[u]) if (v != p) {
dfs(v, u);
mx[u] = max(mx[u], mx[v]);
}
}
const int LG = 16;
struct segment_tree {
int n;
const int INF = -(int)1e6;
vector<int> t, lz;
segment_tree () {};
segment_tree (int _n) {
n = _n;
t.resize(4 * n + 7);
lz.resize(4 * n + 7);
}
void set_off(int id, int l, int r, int u, int v) {
if (l > v or r < u) return ;
if (l >= u and r <= v) {
t[id] = INF;
lz[id] = -1;
return ;
}
if (lz[id] == -1) {
t[id << 1] = t[id << 1 | 1] = INF;
lz[id << 1] = lz[id << 1 | 1] = -1;
lz[id] = 0;
}
int m = (l + r) >> 1;
set_off(id << 1, l, m, u, v);
set_off(id << 1 | 1, m + 1, r, u, v);
t[id] = max(t[id << 1], t[id << 1 | 1]);
}
void set_off(int l, int r) {
++l, ++r;
set_off(1, 1, n, l, r);
}
void update(int id, int l, int r, int p, int val) {
if (l == r) return void(t[id] = val);
if (lz[id] == -1) {
t[id << 1] = t[id << 1 | 1] = INF;
lz[id << 1] = lz[id << 1 | 1] = -1;
lz[id] = 0;
}
int m = (l + r) >> 1;
if (p <= m)
update(id << 1, l, m, p, val);
else
update(id << 1 | 1, m + 1, r, p, val);
t[id] = max(t[id << 1], t[id << 1 | 1]);
}
void set_on(int p, int val) {
++p;
update(1, 1, n, p, val);
}
int get(int id, int l, int r, int u, int v) {
if (l > v or r < u) return 0;
if (l >= u and r <= v) return t[id];
if (lz[id] == -1) {
t[id << 1] = t[id << 1 | 1] = INF;
lz[id << 1] = lz[id << 1 | 1] = -1;
lz[id] = 0;
}
int m = (l + r) >> 1;
return max(get(id << 1, l, m, u, v),
get(id << 1 | 1, m + 1, r, u, v));
}
int get(int l, int r) {
++l, ++r;
return get(1, 1, n, l, r);
}
};
int sp[N][LG + 1], lg[N];
int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
n = N, m = M;
FOR(i, 0, n - 1) {
g[i].clear();
L[i] = n;
R[i] = mx[i] = 0;
}
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n - 1; ++j)
a[i][j] = S[i][j];
}
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n - 1; ++j) {
maxi(R[a[i][j]], j);
mini(L[a[i][j]], j);
}
}
FOR(i, 1, n - 1) {
g[F[i]].push_back(i);
}
dfs(0, -1);
vector<int> d(n, 0);
vector<int> dp(n, -1);
FOR(i, 0, n - 1) {
d[i] = n;
for(int t = 0; t < m; ++t) {
mini(d[i], L[a[t][i]]);
}
}
auto get = [&](int l, int r) {
int j = lg[r - l + 1];
return max(sp[l][j], sp[r - (1 << j) + 1][j]);
};
for(int i = 0; i < n - 1; ++i) {
sp[i][0] = mx[a[0][i]];
}
for(int j = 1; (1 << j) < n; ++j)
for(int i = 0; i + (1 << j) - 1 < n; ++i) {
sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
}
FOR(i, 2, n) lg[i] = lg[i / 2] + 1;
stack<int> st;
segment_tree IT(n);
for(int i = 0; i < n - 1; ++i) {
int lb = 0, rb = i;
int r = i + 1;
while (lb <= rb) {
int mid = (lb + rb) >> 1;
if (get(mid, i) <= i) {
r = mid;
rb = mid - 1;
} else
lb = mid + 1;
}
while (st.size()) {
int u = st.top();
if (d[u] > d[i]) {
st.pop();
} else
break ;
}
int b = (st.size() ? st.top() + 1 : 1);
IT.set_off(b, i);
if (b == d[i]) {
if (b == 0 or dp[b - 1] != -1)
IT.set_on(b, (b > 0 ? dp[b - 1] : 0));
}
st.push(i);
if (r <= i and get(0, i) <= i) {
maxi(dp[i], IT.get(r, i) + 1);
}
}
return dp[n - 2];
}
#ifdef LOCAL
void taskcase() {
int N, M;
assert(2 == scanf("%d%d", &N, &M));
std::vector<int> F(N);
F[0] = -1;
for (int i = 1; i < N; ++i)
assert(1 == scanf("%d", &F[i]));
std::vector<std::vector<int>> S(M, std::vector<int>(N - 1));
for (int i = 0; i < M; ++i)
for (int j = 0; j < N - 1; ++j)
assert(1 == scanf("%d", &S[i][j]));
printf("%d\n", solve(N, M, F, S));
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
freopen("main.inp", "r", stdin);
freopen("main.out", "w", stdout);
int T;
assert(1 == scanf("%d", &T));
while(T--) taskcase();
return 0;
}
#endif
