XMEN  XMEN
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.
ach test case starts with an integer N, size of DNA.
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.
Sample Input :
2 2 1 2 2 1 3 1 2 3 1 3 2
Sample Output :
1 2
Constraints :
1 ≤ T ≤ 10
1 ≤ N ≤ 100000
hide comments
atiq:
20171013 03:20:53
Nice problem to practice n lg n LIS. Thank you. What's the number of this problem? Last edit: 20171013 04:04:18 

cichipi_:
20170910 16:39:01
nice problem!


vengatesh15:
20161227 14:15:05
it is constantly throwing runtime error i don't know why pls any suggestion 

Anuj Arora:
20160816 22:29:30
100th 

Archit Gupta:
20160211 21:34:24
can someone clarify how mapping guarantees the optimal solution ?


anando_du:
20150906 20:17:55
nlogk solution is acceptable ... This problem is not LCS .. It's actually a LIS problem .. All u need to do , u just need to convert it into a lis problem .. (Converting is not too much difficult . just think one DNA as index and other DNA as element , now map them ) 

kerpoo:
20150831 17:55:50
nlogn 

Gohan:
20150717 19:46:59
The O(n^2) Dynamic Programming solution gave TLE.


Naman Goyal:
20150516 00:30:22
The problem statement doesn't clear if it's LCS between digits or each number is considered as individual symbol? 

saumya:
20150126 08:25:11
Longest Common/ Increasing Subsequence ( DP ) Last edit: 20150126 08:34:05 
Added by:  smit hinsu 
Date:  20130218 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  CodeCraft 13 , Author : Nadeem Moidu 