XMEN - X-MEN

Dr. Charles Xavier is trying to check the correlation between the DNA samples of Magneto and Wolverine. Both the DNAs are of length N, and can be described by using all integers between 1 to N exactly once. The correlation between two DNAs is defined as the Longest Common Subsequence of both the DNAs.

Help Dr. Xavier find the correlation between the two DNAs.

Input

First line of input contains number of test cases T. Each test case starts with an integer N, size of DNA. The next two lines contains N integers each, first line depicting the sequence of Magneto's DNA and second line depicting Wolverine's DNA.

Output

For each test case print one integer, the correlation between the two DNAs.

Example

Input:
2
2
1 2
2 1
3
1 2 3
1 3 2

Output:
1
2

Constraints

1 ≤ T ≤ 10
1 ≤ N ≤ 100000


Added by:smit hinsu
Date:2013-02-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:CodeCraft 13 , Author : Nadeem Moidu

hide comments
2014-12-29 21:04:23 Adi
any hint pls!!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.