调整排列

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

给你一个正整数N,再给你两个N的全排列,现在你的任务是用最少的步骤把一个全排列调整为另一个全排列。调整的时候,可以把一个元素移动到该排列的任何一个位置。

比如N=4,下面给出两个N的全排列。1 2 3 4 1 2 4 3,可以把第一个排列中的4移动到3前面,这样就变成了1 2 4 3和第二个排列一样了,那么答案就是1

Input

第一行包含一个数T(1<=T<=20),代表下面共有T组测试数据。 针对每组测试数据: 第一部分输入一个数N,代表序列长度。(1<=N<=100000) 第二部分两行,分别为N的两个全排列。

Output

针对每组测试数据,输出最少的移动步骤。

Sample Input

1
4
1 2 3 4
1 2 4 3

Sample Output

1

Hint

Source

from friend

提交代码