You're given an array A of N integers. You need to find the minimum cost of creating another array B of N integers with the following properties

B_{i} ≥ 0 for each 1 ≤ i ≤ N
The GCD of adjacent elements of B is equal to $1, i.e, \gcd(B_{i}, B_{i+1}) = 1$ for each 1 ≤ i < N

The cost of creating B is defined as follows:

$\sum_{i=1}^{N} 2^{|A_{i} - B_{i} |}$

Find the minimum possible cost to create the array B. Since the answer can be huge print it modulo 10^{9}+7

Note: You need to minimize the value of total cost of creating the array B, and then print this minimum value modulo 10^{9} + 7. For example, suppose there is a way to create the required B with a cost of 500, and another way to do it with a cost of 10^{9} + 7 (which is $0 \pmod {10^{9} + 7})$. The output in this case would be 500 and not 0.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• The first line of each test case contains an integer N - the length of the array A
• The second line of each test case contains $N space-separated integers A_{1},A_{2},\ldots,A_{N}$

------ Output Format ------

For each test case, output on a new line the minimum cost of creating the array B, modulo 10^{9} + 7.

------ Constraints ------

$1 ≤ T ≤ 150$
$1 ≤ N ≤ 10^{4}$
$1 ≤ A_{i} ≤ 10^{6}$
- The sum of $N$ over all test cases won't exceed $10^{4}$.

----- Sample Input 1 ------
3
3
15 16 19
2
5 10
7
9 15 7 19 10 7 1

----- Sample Output 1 ------
3
3
8
----- explanation 1 ------
Test case $1$: The given input already satisfies all the conditions, hence we can take $B = A$ with a cost of $2^{0} + 2^{0} + 2^{0} = 3$.

Test case $2$: One optimal way is to choose $B$ as $ [ 5, 11 ] $, with a cost of $2^{0} + 2^{1} = 3$.

见题面

见题面