최대공약수 행렬의 행렬식

집합 $S = \{x_1, x_2, \ldots, x_n\}$가 약수에 대해 닫혀 있다는 것은, 모든 $x_i \in S$에 대해 $x_i$의 모든 약수 $d$가 $d \in S$를 만족한다는 뜻입니다.

약수에 대해 닫힌 집합 $S$로 최대공약수 행렬 $(S) = (s_{ij})$를 만듭니다. 여기서 $s_{ij} = \gcd(x_i, x_j)$입니다. 이 행렬의 행렬식(determinant)을 구하는 프로그램을 작성하세요.

$D_n = \begin{vmatrix} \gcd(x_1,x_1) & \gcd(x_1,x_2) & \cdots & \gcd(x_1,x_n) \\ \gcd(x_2,x_1) & \gcd(x_2,x_2) & \cdots & \gcd(x_2,x_n) \\ \vdots & \vdots & \ddots & \vdots \\ \gcd(x_n,x_1) & \gcd(x_n,x_2) & \cdots & \gcd(x_n,x_n) \end{vmatrix}$

첫째 줄에 테스트 케이스의 개수 $T$가 주어집니다. 각 테스트 케이스의 첫째 줄에는 집합 $S$의 원소 개수 $n$ ($0 < n < 1000$)이 주어집니다. 다음 줄에는 집합의 원소 $x_1, x_2, \ldots, x_n$이 주어집니다. ($0 < x_i < 2 \times 10^9$이고, 각 $x_i$는 정수입니다.)

각 테스트 케이스마다 입력으로 주어진 집합 $S$의 최대공약수 행렬식을 $1{,}000{,}000{,}007$으로 나눈 나머지를 출력합니다.