Chef and the Cards

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
There are N cards placed in a row, where every card has two numbers written on it, one on the top and
one on the bottom. The numbers are between 1 and N (both inclusive). Every number is written on the top of exactly one card, and on the bottom of exactly one card as well.
Chef wants to rearrange the cards, such that the length of the longest common contiguous subsequence between the sequence formed by number written on top of the cards, and that formed by those written on the bottom is maximum. He can't modify the numbers written on any card and can't flip the cards, that is, for any card the number written on top remains at the top and the number written on bottom stays at the bottom. Find out the maximum possible length of the common contiguous subsequence.
Input
The first line of input contains an integer T denoting the number of test cases.
 The first line of each test
case contains an integer N.  The next line contains N space separated integers A_{1}, A_{2}, ... , A_{N}, where A_{i}(1 ≤ i ≤ N) is the number written on the top of the ith card.
 The next line contains N space separated integers B_{1}, B_{2}, ... , B_{N}, where B_{i}(1 ≤ i ≤ N) is the number written at the bottom of the ith card.
Output
For each test case, output a single line containing the integer L: the maximum length of the longest common contiguous subsequence.
Constraints
 1 ≤ T ≤ 100
 1 ≤ N ≤ 2000
 1 ≤ A_{i}, B_{i} ≤ N
 All the elements in both arrays A and B are distinct.
Example
Input: 2 3 1 3 2 2 1 3 8 3 8 4 2 6 1 5 7 5 2 4 3 8 7 6 1 Output: 2 4
Explanation
First Example :
One of the possible card arrangements is:
1 2 3
2 3 1
Length of the longest common contiguous subsequence between [1, 2, 3] and [2, 3, 1] is 2, [2, 3]. And that's the maximum possible, so answer is 2.
Second Example:
One of the possible card arrangements is :
7 3 2 8 6 5 4 1
1 5 3 2 8 6 4 7
The longest common contiguous subsequence has length 4 [3, 2, 8, 6] here. There is no way to arrange these cards such that it's more than 4.
Note
Let L be the answer. Let C_{i} be the value written on the top of the card at i^{th} position and D_{i} be the value written on the bottom of the card at i^{th} position after rearranging. Then, there should be a pair (x, y) (1 ≤ x,y ≤ NL+1) such that the condition C_{x+j} = D_{y+j} is satisfied for all j, where 0 ≤ j < L.
Author:  rustinpiece 
Tester:  iscsi 
Editorial  http://discuss.codechef.com/problems/CARDLINE 
Tags  cook61, dynamicprogramming, graphs, greedy, mediumhard, rustinpiece 
Date Added:  31072015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 