Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

New Recruitment

By Ishtiaq · 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.

    Discussion

    Statistics


    67% Solution Ratio

    RAB_27Earliest, 1M ago

    LUMBERJACK_MANFastest, 0.2s

    pathanLightest, 7.4 MB

    Deshi_TouristShortest, 1122B

    Submit

    Login to submit

    Editorial

    Prerequisites: Prefix Function/ Z-Function Explanation: Let, first of all, we are asked to find the ...