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 ith end point on one side can only end on the ith 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 non-cutting 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<=103). The second line contains x-coordinates of end points identified on the first side and similiarly the third line contains the x-coordinates of corresponding end points identified on the other side. The end points are inputted in the order in which they were identified. The x-coordinates can range between -103 to 103.

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:
3

4

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 non-overlapping bridges can be formed between the 3rd and 4th end points on each side.


hide comments
nikhil_more: 2019-10-03 15:44:06

Last edit: 2019-10-03 16:50:03
payal2621: 2019-08-19 15:48:29

14

First consider the pairs: (2,6), (5, 4), (8, 1), (10, 2), sort it according to the first element of the pairs (in this case are already sorted) and compute the list on the second element of the pairs, thus compute the LIS on 6 4 1 2, that is 1 2. Therefore the non overlapping lines you are looking for are (8, 1) and (10, 2).

ankit0107verma: 2019-06-01 06:51:39

Use the concept of LIS with order of pairs in mind easy cake problem

shivam_jain: 2019-05-29 13:46:04

A simple problem made very difficult because of not having proper explanation
Read Shashank Tiwari's comment

Last edit: 2019-05-29 13:46:44
thanos_tapras: 2019-03-11 10:25:20

Finally got AC.
Make sure to check if your answer works for multiple points on the same x coordinate.
e.g.
1 1 2
1 1 1

Last edit: 2019-03-11 10:25:35
beginner: 2019-02-10 20:15:31

got WA because of improper comparator. Finally got AC

whyamievenhere: 2018-12-23 18:40:27

Really no need of trees/binary search. Simple dp suffices..

mhasan01: 2018-12-15 14:24:32

AC in one go using LIS!

mayurcoder: 2018-08-17 08:15:33

Very strict timing for JAVA.

atulrulers: 2018-07-14 23:14:10

Beautiful question to learn LIS


Added by:Troika::Bytes
Date:2010-02-18
Time limit:0.193s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC GAWK MAWK BC C-CLANG CPP14 CPP14-CLANG CLOJURE COBOL COFFEE D-CLANG D-DMD DART ELIXIR FSHARP FANTOM FORTH GO GOSU GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PERL6 PICO PROLOG PYPY PYTHON3 PY_NBC R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET