K. The Red Tomato
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Eddard and his secret partner found a really cute song called "I am the red tomato" and they really loved it, but something piqued their interest..

"I am the red tomato, planted among the vegetables. You eat me until you're full, and your cheeks go red."

The mystery here is.. how much tomato can they eat?

Eddard and his partner have a hypothesis: The maximum total weight of tomatoes they can eat at one sitting is $$$w$$$ grams, regardless of the number of tomatoes. For example, if $$$w = 9$$$, they can eat 3 tomatoes of weights $$$6, 2, 1$$$, as their total weight is $$$9$$$, but they can't eat 2 tomatoes of weights $$$7, 4$$$, as their total weight is $$$11$$$.

The goal is to find the value $$$w$$$. So, they decided to run the following experiment $$$e$$$ times:

They put $$$n$$$ tomatoes of weights $$$a_1, a_2, ..., a_n$$$ on a table. Then, they start eating the tomatoes from left $$$(1)$$$ to right $$$(n)$$$ until they can't eat any more tomatoes. After they're done, they write down the number of tomatoes left $$$m$$$.

For example, if $$$w = 5$$$, $$$a = [3, 4, 2]$$$, they will eat the first tomato of weight $$$3$$$ then stop since they can't eat the second tomato, as the total weight would be $$$7$$$. They will, then, write down $$$m = 2$$$ as the number of remaining tomatoes.

Can you help them find the value $$$w$$$ after running multiple experiments?

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \le t \le 10^4)$$$. The description of the test cases follows.

The first line of each test case contains a single integer $$$e$$$ $$$(1 \le e \le 10^6)$$$ – The number of experiments they are running. The description of the experiments follows.

The first line of each experiment contains $$$2$$$ integers $$$n, m$$$ $$$(1 \le n \le 10^6, 0 \le m \le n)$$$ – The number of tomatoes at the start and the end of the experiment, respectively.

The second line of each experiment contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ $$$(1 \le a_i \le 10^9)$$$ – The weights of the tomatoes.

It is guaranteed that sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$

Output

For each test case, print a single integer $$$w$$$ $$$(0 \le w \le 10^{18})$$$ – the answer.

If multiple answers exist, print the smallest. if no answer exists, print "False Hypothesis".

Example
Input
4
3
1 0
5
3 2
3 4 2
5 1
1 2 1 1 1
2
1 0
5
1 1
6
1
1 1
100
2
3 0
3 5 6
4 1
1 4 2 4
Output
5
5
0
False Hypothesis
Note

In the first test case, $$$3$$$ experiments are run:

  • In the first experiment, $$$a = [5]$$$, $$$m = 0$$$, which means they ate the only tomato with weight $$$5$$$.
  • In the second experiment, $$$a = [3, 4, 2]$$$, $$$m = 2$$$, which means they ate only the first tomato with weight $$$3$$$ and couldn't eat anymore.
  • In the third experiment, $$$a = [1, 2, 1, 1, 1]$$$, $$$m = 1$$$, which means they ate the first $$$4$$$ tomatoes with a total weight of $$$5$$$, but couldn't eat the last tomato.

From these $$$3$$$ experiments, it can be deduced that the smallest possible value for $$$w$$$ is $$$5$$$

In the fourth test case, after running the $$$2$$$ experiments, it can be deduced that no value $$$w$$$ exists that satisfies both experiments. Thus, the hypothesis is false.