정사각형 자르기

두 사람이 직사각형 종이 한 장을 번갈아 자른다. 종이의 긴 변 길이는 $L$, 짧은 변 길이는 $W$이다.

차례가 된 사람은 남아 있는 직사각형에서 잘라낼 수 있는 가장 큰 정사각형을 자른다. 짧은 변이 $W$인 직사각형에서 잘라낼 수 있는 가장 큰 정사각형은 한 변이 $W$인 정사각형이다. 한 차례에 이 크기의 정사각형을 하나 이상 잘라내고, 한 차례에 잘라낸 정사각형은 모두 크기가 같으며, 자르고 남은 부분은 직사각형 한 조각이어야 한다. 남는 부분 없이 종이를 다 자른 사람이 이긴다.

한 판의 기록은 $L\ W\ r\ a_1\ a_2\ \dots\ a_r$ 순서로 적는다. $r$은 차례의 수이고 $a_i$는 $i$번째 차례에 잘라낸 정사각형의 개수다. 예를 들어 긴 변이 5이고 짧은 변이 2인 종이에서 먼저 자르는 사람이 한 변이 2인 정사각형 2개를 잘라내면 $2 \times 1$ 직사각형이 남고, 다음 사람이 한 변이 1인 정사각형 2개를 잘라내며 판이 끝난다. 이 판의 기록은 5 2 2 2 2 이다.

전산 장애로 각 기록의 앞 두 수 $L$과 $W$가 지워졌다. 남아 있는 $r$과 $a_1$부터 $a_r$까지만 보고 $L$을 복원하라. 가능한 $L$이 여러 개면 가장 작은 값을 답으로 한다.

첫 줄에 기록의 수 $M$이 주어진다.

다음 $M$개 줄에 기록이 한 줄에 하나씩 주어진다. 각 줄은 차례의 수 $r$로 시작하고, 이어서 $a_1$부터 $a_r$까지 $r$개의 정수가 공백으로 구분되어 주어진다.

• $1 \le M \le 20$
• $1 \le r \le 50$
• $1 \le a_i \le 100$
• 모든 기록은 실제로 진행할 수 있는 판에서 나온 기록이다. 따라서 $r \ge 2$이면 $a_r \ge 2$이다.
• 원래 종이의 크기는 $1 \le W \le L \le 10^{100}$을 만족한다.

$M$개 줄을 출력한다. $i$번째 줄에는 $i$번째 기록이 나올 수 있는 직사각형 가운데 긴 변이 가장 짧은 것의 $L$ 값을 출력한다.