#483 Dadas's Ramen Mukbang

Statement

Statement language

Dadas is going to eat $N$ bowls of ramen one by one. Fully cooking the $i$ -th bowl takes $A_i$ units of time.

For each bowl, Dadas waits for at most $K$ units of time. Therefore, the actual waiting time before eating the $i$ -th bowl is $\min(A_i,K)$ . Eating takes $0$ time, and only one bowl is prepared at a time.

Thus, the total time until all bowls are eaten is

\sum_{i=1}^N \min(A_i,K).

It is guaranteed that there exists at least one positive integer $K$ for which the total time is exactly $L$ . Find the minimum such $K$ .

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the minimum positive integer $K$ satisfying the condition on one line.

Constraints

$1 \le T \le 200\,000$ .
$1 \le N \le 200\,000$ .
$1 \leq_{}$ ().

Subtasks

#	Score	Constraints
1	30	$A_i \le 1\,000$ ( $1 \le i \le N$ ).

Samples

Input

Output

2
4
10