작은 청록색 물고기는 길이가 $n$인 음이 아닌 정수열 $a_1,a_2,\ldots,a_n$을 가지고 있습니다. 작은 청록색 물고기는 다음 연산을 원하는 만큼(0번 포함) 수행할 수 있습니다:

• 정수 $1 \le i \le n$을 하나 선택합니다.
• $a_i$를 $\operatorname{mex}_{1\le k<i}a_k$로 변경합니다.

여기서, 음이 아닌 정수들의 집합 $S$에 대하여 $\operatorname{mex} S$라는 표기는 집합 $S$에 나타나지 않는 가장 작은 음이 아닌 정수로 정의됩니다. 예를 들어, $\operatorname{mex}\{0,1,2,4,6\}=3$, $\operatorname{mex}\{1,2,3\}=0$, $\operatorname{mex}\varnothing=0$입니다.

작은 청록색 물고기는 몇 번의 연산(0번일 수도 있음)을 통해 $a_n$의 값을 가능한 한 크게 만들고 싶어 합니다. 작은 청록색 물고기는 여러분이 다음을 계산하기를 원합니다:

1. 임의의 횟수만큼 연산을 수행한 후 얻을 수 있는 $a_n$의 최댓값;
2. 1번 조건을 만족하는 상태에서, 이 최댓값을 달성하기 위해 필요한 최소 연산 횟수.

Input

여러 개의 테스트 케이스가 주어집니다. 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 단일 정수 $T$ ($1 \le T$)가 주어집니다.

각 테스트 케이스에 대해, 첫 번째 줄에는 수열의 길이를 나타내는 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다.

다음 줄에는 $n$개의 정수 $a_1,a_2,\ldots,a_n$ ($0 \le a_i \le 10^9$)이 주어집니다.

모든 테스트 케이스에 대한 $n$의 합은 $10^6$을 초과하지 않음이 보장됩니다.

Output

각 테스트 케이스마다 두 개의 정수를 한 줄에 출력합니다. 첫 번째 정수는 $a_n$의 최댓값을 나타내고, 두 번째 정수는 필요한 최소 연산 횟수를 나타냅니다.

Examples

Input 1

4
2
0 114514
3
0 1 0
4
3 1 2 0
6
6 5 4 3 2 1

Output 1

114514 0
2 1
3 2
5 3