배열 $a_1, a_2, \ldots, a_n$의 소화를 다음과 같이 정의하자.

• 길이가 $n$인 임의의 순열 $p_1, p_2, \ldots, p_n$을 선택한다. 순열은 $1$부터 $n$까지의 정수가 각각 정확히 한 번씩 나타나는 배열이다.
• 모든 $i$에 대해 $a_i := a_i \bmod \max(a_{p_i}, 1)$을 동시에 수행한다.
• 배열에서 제거할 임의의 수 $a_i$를 선택하고, 나머지 원소들을 이어 붙여 새로운 배열 $a_1, a_2, \ldots, a_{n-1}$을 만든다. 이 배열이 소화 연산의 결과이다.

이 절차로 얻을 수 있는 모든 배열은 소화 연산의 결과가 될 수 있다.

$1$부터 $n$까지의 정수로 이루어진 배열 $a_1, a_2, \ldots, a_n$이 주어진다. 이 배열에 소화 연산을 연속으로 $n-1$번 수행한 뒤 얻을 수 있는 $a_1$의 최댓값은 얼마인가?

입력

각 테스트는 여러 테스트 케이스로 이루어진다. 첫 번째 줄에는 테스트 케이스의 수인 정수 $t$ ($1 \le t \le 10^4$)가 주어진다. 다음 줄들에는 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 배열 $a$의 길이인 정수 $n$ ($1 \le n \le 2 \cdot 10^5$)이 주어진다.

각 테스트 케이스의 두 번째 줄에는 배열 $a$의 원소인 $n$개의 정수 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$)이 주어진다.

모든 테스트 케이스에 대한 $n$의 합은 $2 \cdot 10^5$를 넘지 않음이 보장된다.

출력

각 테스트 케이스에 대해 얻을 수 있는 $a_1$의 최댓값을 출력한다.

예제

입력 1

1
3
3 2 2

출력 1

1