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.

Input

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

Output

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.

Note

In the first test case, all elements cannot be made special at the same time.

In the second test case, performing $$$5$$$ operations results in the array $$$[30,72]$$$, whose elements are all special.

In the fourth test case, the array becomes $$$[9557358]$$$ after $$$7$$$ operations.

Six Seven

Examples