Background

Special for beginners, ^_^

Description

给出一个长度为 $n$ 的置换 $p$ 和颜色数组 $c$ 。

求最小的 $k$ ,使 $p^{k}$ 中存在一个“同色环”。即存在 $i$ ，使 $p^{k}[i]$, $p^{k}[p^{k}[i]]$

,…，全部同色。

其中 $p^{2}[i]=p[p[i]],p^{3}[i]=p[p[p[i]]]$ ,…。

Format

Input

第一行一个正整数 $T(\le10^6)$.，表示数据组数。

对于每组数据，包含三行：

第一行一个整数, $n（\le10^6）$ 。

第二行 $n$ 个整数, 表示 $p$ 。

第三行 $n$ 个整数, 表示 $c(\le10^6)$ 。

题目保证单个测试点的 $n$求和不超过 $\le10^6$。

Output

对于每组数据，在一行中输出一个数，表示答案。

Samples

3
4
1 3 4 2
1 2 2 3
5
2 3 4 5 1
1 2 3 4 5
8
7 4 5 6 1 8 3 2
5 3 6 4 7 5 8 4

1
5
2

Limitation

1s, 1024KiB for each test case.