Mr. Azad applied for a job. During his interview, the interviewer gave him the following task to solve:
Given two arrays and consisting of integer numbers, find out the beauty value of each prefix of array . The beauty value for a prefix of Length of the prefix Number of segments where that prefix overlaps with array .
Let, and then for each prefix of the beauty value is computed as follows:
Beauty of prefix (Since the length of the prefix and overlaps with four different segments of , starting positions of the segments are: )
Beauty of prefix (Since the length of the prefix and overlaps with two different segments of , starting positions of the segments are: )
Beauty of prefix (Since the length of the prefix and overlaps with one segment of , starting position of the segment is: )
Since the interview time is very short, the interviewer was only interested in the prefix that has the maximum beauty value. If multiple prefixes had the same beauty value then Mr. Azad had to find the longest prefix that had the maximum beauty value.
Gladly Mr. Azad solved the problem and got the job offer! Can you solve it too?
The first line contains an integer , the number of test cases.
The first line of each test case contains two integers , the number of elements in array and the number of elements in array respectively.
The second line of each test case contains integers , the elements of array .
The third line of each test case contains integers , the elements of array .
For each test case, print the length of the longest prefix having maximum beauty value.
Input | Output |
---|---|
2 3 6 1 1 2 1 3 1 1 1 2 4 10 3 1 2 5 3 1 2 3 1 2 3 1 2 7 | 2 3 |
For the 1st test case
(Explained in the description) prefixes of length and have the maximum beauty value but we are interested in maximum prefix length, hence the answer is .
For the 2nd test case
prefix of length has beauty value
prefix of length has beauty value
prefix of length has beauty value
prefix of length has beauty value
Prefix with length has the maximum beauty value.