Determinant of the GCD Matrix

A set $S = \{x_1, x_2, \ldots, x_n\}$ is closed under divisors if, for every $x_i \in S$, every divisor $d$ of $x_i$ also satisfies $d \in S$.

From a divisor-closed set $S$, build the greatest common divisor matrix $(S) = (s_{ij})$ where $s_{ij} = \gcd(x_i, x_j)$. Write a program that computes the determinant of this matrix.

$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}$

The first line contains the number of test cases $T$. For each test case, the first line contains the number of elements $n$ ($0 < n < 1000$) of the set $S$. The next line contains the elements $x_1, x_2, \ldots, x_n$ ($0 < x_i < 2 \times 10^9$, and each $x_i$ is an integer).

For each test case, print the determinant of the greatest common divisor matrix of the given set $S$ modulo $1{,}000{,}000{,}007$.