집에서 따라 하지 마세요

정수 배열 $b$에 대해 $f(b)$를 다음과 같이 정의합니다. $f(b)$는 $b$와 길이가 같은 배열 중에서, 사전순으로 $b$보다 크고 원소의 집합이 $b$의 원소의 집합과 같은 배열 가운데 사전순으로 가장 작은 배열입니다. 그런 배열이 없으면 $f(b)$는 정의되지 않습니다. 예를 들어 $f([2,7,7,5,4]) = [4,2,2,5,7]$입니다. 여기서 배열의 원소 집합은 각 값을 몇 번 나타나든 한 번만 센 값들의 모임입니다. 배열 $[2,7,7,5,4]$와 $[4,2,2,5,7]$은 값마다 나타나는 횟수가 달라도 원소 집합이 $\{2,4,5,7\}$로 같습니다.

$f^k(b)$는 $f$를 $k$번 적용한 결과를 뜻합니다. 정의되지 않은 값에 $f$를 적용한 결과도 정의되지 않습니다. 예를 들어 $f^2([2,7,7,5,4]) = f([4,2,2,5,7]) = [4,2,2,7,5]$입니다.

길이가 $n$인 정수 배열 $a$가 주어집니다. 이 배열은 추가 조건을 만족하며, 배열 $a$에서 정확히 한 번 나타나는 정수가 적어도 하나 있습니다. 다음 조건 중 적어도 하나를 만족하는 $f^k(a)$가 되는 가장 작은 양의 정수 $k$를 구하세요. $f^k(a)$는 정의되어 있어야 합니다. 그런 $k$가 없으면 -1을 출력합니다.

• $a$에서 정확히 한 번 나타나는 정수가 $f^k(a)$에서는 두 번 이상 나타난다.
• $a$에서 두 번 이상 나타나는 정수가 $f^k(a)$에서는 정확히 한 번 나타난다.

답이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 구하세요.

입력에는 하나 이상의 테스트 케이스가 포함됩니다. 첫 줄에는 테스트 케이스의 개수 $t$ ($1 \le t \le 10^5$)가 주어집니다.

각 테스트 케이스는 두 줄로 주어집니다. 첫 줄에는 $n$ ($2 \le n \le 10^5$)이 주어지고, 둘째 줄에는 정수 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^6$) 이 주어집니다. $a$에는 정확히 한 번 나타나는 값이 적어도 하나 있습니다.

모든 테스트 케이스의 $n$의 합은 $6 \cdot 10^5$을 넘지 않습니다.

각 테스트 케이스마다 답을 $10^9 + 7$로 나눈 나머지를 한 줄에 출력합니다. 답이 없으면 -1을 출력합니다.