New Recruitment

Ishtiaq CUET Intra University Jun...
Limits 1s, 256 MB

Mr. Azad applied for a job. During his interview, the interviewer gave him the following task to solve:

Given two arrays AA and BB consisting of integer numbers, find out the beauty value of each prefix of array AA. The beauty value for a prefix of AA == ((Length of the prefix)) * ((Number of segments where that prefix overlaps with array BB)).

Let, A=[1,1,2]A = [1, 1, 2] and B=[1,3,1,1,1,2]B = [1, 3, 1, 1, 1, 2] then for each prefix of AA the beauty value is computed as follows:

Beauty of prefix [1]=14=4[1] = 1\cdot 4 = 4 (Since the length of the prefix =1=1 and [1][1] overlaps with four different segments of BB, starting positions of the segments are: 1,3,4,51, 3, 4, 5)

Beauty of prefix [1,1]=22=4[1, 1] = 2\cdot 2=4 (Since the length of the prefix =2=2 and [1,1][1, 1] overlaps with two different segments of BB, starting positions of the segments are: 3,43, 4)

Beauty of prefix [1,1,2]=31=3[1, 1, 2] = 3\cdot 1=3 (Since the length of the prefix =3=3 and [1,1,2][1, 1, 2] overlaps with one segment of BB, starting position of the segment is: 44)

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?

Input

The first line contains an integer T(1T10)T (1\leq T\leq 10), the number of test cases.

The first line of each test case contains two integers N,M(1N,M2105)N, M (1\leq N,M\leq 2\cdot 10^5), the number of elements in array AA and the number of elements in array BB respectively.

The second line of each test case contains NN integers A1,A2,,AN(1Ai109)A_1, A_2, …, A_N (1\leq A_i\leq 10^9), the elements of array AA.

The third line of each test case contains MM integers B1,B2,,BM(1Bi109)B_1, B_2, …, B_M (1\leq B_i\leq 10^9), the elements of array BB.

Output

For each test case, print the length of the longest prefix having maximum beauty value.

Sample

InputOutput
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 11 and 22 have the maximum beauty value but we are interested in maximum prefix length, hence the answer is 22.

For the 2nd test case

prefix of length 11 has beauty value =13=3= 1\cdot 3 = 3

prefix of length 22 has beauty value =23=6= 2\cdot 3 = 6

prefix of length 33 has beauty value =33=9= 3\cdot 3 = 9

prefix of length 44 has beauty value =40=0= 4\cdot 0 = 0

Prefix with length 33 has the maximum beauty value.

Submit

Login to submit.

Contributors

Statistics

65% Solution Ratio
RAB_27Earliest, Jun '21
LUMBERJACK_MANFastest, 0.2s
Hamim_Lightest, 7.1 MB
Deshi_TouristShortest, 1122B
Toph uses cookies. By continuing you agree to our Cookie Policy.