For positive integers $i$ and $j$, define $f_i(j)$ as the maximum integer $k$ such that $i^k$ divides $j$. A number $j$ is considered special if $f_6(j) \gt f_7(j)$. For example, $6$ is special, but $67$ and $7$ are not.

You are given an array $a$ of $n$ positive integers. In one operation, you must increase every element in the array by $1$.

Your task is to find the minimum number of operations needed to make all elements in $a$ special at the same time, or determine that it is impossible.

The first line contains an integer $t$ ($1 \leq t \leq 10^4$), the number of test cases.

For each test case, the first line contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$).

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$).

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

For each test case, output a single integer: the minimum number of operations to make all elements special at the same time, or $-1$ if it is impossible.