Description

给出两个长度为N (1<=N<=20000) 的数字串 (分别由1~N的整数构成，每个整数出现一次)，其中A串为第一密码串，而B串为第二密码串，真正的密码串C为A、B串的最长公共子序列（非必须连续），请输出C串的长度。

Input

第一行为整数T（T<=20）表示有T组测试数据。每组测试数据由三行组成，其第一行为N，第二行为A串，三行为B串。

Output

由T行组成，每行一个整数表示真正密码C串的长度。

Sample

Input

3
3
1 2 3
1 2 3
3
3 1 2
3 2 1
3
3 2 1
1 2 3

Output

3
2
1

Source: 超人