BRIDGE  Building Bridges
The tribe soon discovers that just communication is not enough and wants to meet each other to form a joint force against the terminator. But there is a deep canyon that needs to crossed. Points have been identified on both sides on which bridge ends can be made. But before the construction could be started, a witch Chudael predicted that a bridge can only be built between corresponding end points, i.e. a bridge starting from the i^{th} end point on one side can only end on the i^{th} end point on the other side, where the position of end points is seen in the order in which the points were identified. If not, it would lead to the end of the tribe. The tribe just wants to make as many noncutting bridges as possible, with the constraint in mind. Bridges "cut" if and only if they have exactly one common point that is not an end point.
Input
The first line of the input contains test cases t (1<=t<=50). It is followed by 3*t lines, 3 for each test case. The first line of input for each test case contains the number of end points identified on each side, n (1<=n<=10^{3}). The second line contains xcoordinates of end points identified on the first side and similiarly the third line contains the xcoordinates of corresponding end points identified on the other side. The end points are inputted in the order in which they were identified. The xcoordinates can range between 10^{3} to 10^{3}.
Output
You are required to output a single line for each test case. The line contains a single integer – the maximum number of bridges possible with the constraints explained above.
Example
Input:
34
2 5 8 10
6 4 1 2
3
5 3 10
6 4 1
6
1 2 3 4 5 6
3 4 5 6 1 2
Output:2
2
4
Expalanation: For the first test case, two nonoverlapping bridges can be formed between the 3rd and 4th end points on each side.
hide comments
akhil_29071991:
20201026 10:23:36
<snip>


azahar_024:
20200504 19:45:36
Can anyone explain why LIS is the solution of this problem... 

akt_114:
20200429 02:00:09
"cut" definition cost me 1 WA :/


vickyvanshaj:
20191229 20:05:54
java gives TLE for O(nlogn), and other are accepted with O(n^2)??wtf?


nikhil_more:
20191003 15:44:06
Last edit: 20191003 16:50:03 

payal2621:
20190819 15:48:29
14


ankit0107verma:
20190601 06:51:39
Use the concept of LIS with order of pairs in mind easy cake problem 

shivam_jain:
20190529 13:46:04
A simple problem made very difficult because of not having proper explanation


thanos_tapras:
20190311 10:25:20
Finally got AC.


beginner:
20190210 20:15:31
got WA because of improper comparator. Finally got AC 
Added by:  Troika::Bytes 
Date:  20100218 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM32GCC GAWK MAWK BC CCLANG CPP14 CPP14CLANG CLOJURE COBOL COFFEE DCLANG DDMD DART ELIXIR FSHARP FANTOM FORTH GO GOSU GRV JSMONKEY KTLN NIM NODEJS OBJC OBJCCLANG OCT PERL6 PICO PROLOG PYPY PYTHON3 PY_NBC R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET 