解题思路

先把排列 $a$ 中每个数所在的位置求出来，记为 $pos[x]$，表示数字 $x$ 在 $a$ 里的下标。

然后按顺序遍历排列 $b$，把它转换成位置序列：

题目内容

给定两个长度为 $n$ 的排列 {$a_1,a_2,...,a_n$} 与 {$b_1,b_2,...,b_n$}。你可以进行如下操作一次：

• 选择一个正整数 $k$，构造数组 $c$，将排列 $a$ 按原顺序在 $c$ 的末尾依次复制 $k$ 份，得到长度为 $k×n$ 的数组 $c$ ；形式化地，对任意 $1≤j≤k$ 与 $1≤i≤n$ ，都有 $c_{i+(j-1)×n}=a_i$。

你希望数组 $c$ 中存在至少一个子序列，其按顺序拼接后与排列 $b$ 完全相同。请计算满足该条件的最小 $k$ 。

排列：长度为 $n$ 的排列是由 $1$ ~ $n$ 这 $n$ 个整数按任意顺序组成的数组，其中每个整数恰好出现一次。

子序列：子序列为从原序列中删除任意个(可以为零，也可以为全部)元素后，保持相对顺序得到的新序列 。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10^4)$ 代表数据组数，每组测试数据描述如下：

• 第一行输入一个整数 $n(1≤n≤2×10^5)$ 表示排列长度；

• 第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≤a_i≤n)$ 表示排列 $a$ ；

• 第二行输入 $n$ 个整数 $b_1,b_2,...,b_n(1≤b_i≤n)$ 表示排列 $b$ 。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$ 。

输出描述

对于每一组测试数据，新起一行。

• 输出一个整数，表示使得 $b$ 能作为 $c$ 的一个子序列出现所需的最小 $k$ 。

样例1

输入

2
5
2 3 1 5 4
3 5 4 2 1
4
1 2 3 4
4 3 2 1

输出

2
4