B'Polycarp has a lot of work to do. Recently he has learned a new time management rule: "if a task takes five minutes or less, do it immediately". Polycarp likes the new rule, however he is not sure that five minutes is the optimal value. He supposes that this value d should be chosen based on existing task list. Polycarp has a list of n tasks to complete. The i -th task has difficulty p_i , i.e. it requires exactly p_i minutes to be done. Polycarp reads the tasks one by one from the first to the n -th. If a task difficulty is d or less, Polycarp starts the work on the task immediately. If a task difficulty is strictly greater than d , he will not do the task at all. It is not allowed to rearrange tasks in the list. Polycarp doesn 't spend any time for reading a task or skipping it. Polycarp has t minutes in total to complete maximum number of tasks. But he does not want to work all the time. He decides to make a break after each group of m consecutive tasks he was working on. The break should take the same amount of time as it was spent in total on completion of these m tasks. For example, if n=7 , p=[3, 1, 4, 1, 5, 9, 2] , d=3 and m=2 Polycarp works by the following schedule: Polycarp stops exactly after t minutes. If Polycarp started a task but has not finished it by that time, the task is not considered as completed. It is allowed to complete less than m tasks in the last group. Also Polycarp considers acceptable to have shorter break than needed after the last group of tasks or even not to have this break at all -- his working day is over and he will have enough time to rest anyway. Please help Polycarp to find such value d , which would allow him to complete maximum possible number of tasks in t minutes. The first line of the input contains single integer c ( 1 <= c <= 5 cdot 10^4 ) -- number of test cases. Then description of c'...