B"This is an interactive problem. Fox gave Cat two positive integers n and k . She has a hidden array a_1, ldots , a_n of length n , such that 1 <= q a_i <= q n for every i . Now they are going to play the following game: For any two integers l, r such that 1 <= q l <= q r <= q n , define f(l, r) = (r - l + 1) cdot max limits_{x=l}^r a_x . In other words, f(l, r) is equal to the maximum of the subarray a_l, ldots, a_r multiplied by its size. Cat can ask Fox at most 2 n questions about the array. He will tell her two integers l and x ( 1 <= q l <= q n, 1 <= q x <= q 10^9 ), and she will tell him one integer p as the answer -- the smallest positive integer r such that f(l, r) = x , or n+1 if no such r exists. Now, Cat needs to find the largest value m such that there exists a sequence c_1, ldots, c_{k-1} such that 1 <= q c_1 < ldots < c_{k-1} < n and f(1, c_1) = f(c_1 + 1, c_2) = ldots = f(c_{k-1}+1, n) = m . If no such m exists, he should indicate this and take -1 as the answer. Note that for k = 1 , m is always equal to f(1, n) . In other words, the goal is to find the largest m such that you can split the array into exactly k subarrays ( k is the constant given to you in the beginning of the interaction) so that all the subarrays have the product of their length and their maximum equal to m , or determine that no such m exists. Every element should belong in exactly one of the subarrays. Cat doesn't know what he should do, so he asked you to play the game for him. Each test contains multiple test cases. The first line contains a single integer t ( 1 <= q t <= q 10^3 ) -- the number of test cases. The description of the test cases follows. The first line of each test case contains two positive integers n and k ( 1 <= q k <= q n <= q 10^4$"...