You are given a set of ‘N’ rectangular envelopes. The height and width of each envelope are given by arrays, ‘height’ and ‘width’ respectively, each consisting of ‘N’ positive integers. The height and width of the ith envelope is given by ‘height[i]’ and ‘width[i]’ respectively.
You can put one envelope inside another envelope if and only if both the height and width of one envelope is strictly greater than the height and width of the other envelope.
What is the maximum number of envelopes you can put one inside the other?
Note:
Rotation of envelope is not allowed, that is, height and width can’t be exchanged.
Input Format:
The first line of input contains an integer ‘T’ denoting the number of test cases. The next 3*T lines represent the ‘T’ test cases. The first line of each test case contains an integer ‘N’, representing the number of envelopes. The second line of the test case contains ‘N’ space-separated integers representing elements of the array ‘height’. The third line of the test case contains ‘N’ space-separated integers representing elements of the array ‘width’.
Output Format :
For each test case, print, in a separate line, the maximum number of envelopes you can Russian doll.
Constraints:
1 <= T <= 50
1 <= n <= 104
1 <= height[i] <= 109
1 <= width[i] <= 109
Test Case 1: The number envelopes, ‘N’ = 4 ‘height’ = {5, 6, 6, 2} ‘width’= {4, 4, 7, 3} Let's denote dimensions of the envelope in (Height, Width) manner then, one way of Russian Doll envelopes in outermost to the innermost manner is as follow: Select the third envelope, i.e., envelope with dimensions (6, 7) as the outermost envelope. Place the first envelope i.e envelope with dimensions (5, 4) inside the outermost envelope. You can do this because both the height and width of this envelope are strictly less than the outermost envelope. Place the fourth envelope i.e envelope with dimensions (2, 3) inside the previous envelope. In this way, we can Russian Doll 3 envelopes. No other way can Russian Doll more than 3 envelopes.
Test Case 2: You can put the second envelope inside the first envelope because both the height and width of the second envelope are strictly less than the first envelope.
