A. Prime Magic
time limit per test
1 с
memory limit per test
512 megabytes
input
standard input
output
standard output

Walk Alone has a sequence $$$a_1,a_2,...,a_n$$$, and he can use a magic on it:

  • Choose an odd prime number $$$p$$$ and an interval $$$[l, r] \subseteq [1,n]$$$ satisfying $$$r-l+1=p$$$ , and then add $$$1$$$ or $$$-1$$$ to every $$$a_i$$$ in this interval. That is, choose $$$x\in \{1, -1\}$$$, then $$$\forall i \in [l, r], a_i \leftarrow a_i+x$$$.

Remind that odd prime is numbers that are odd greater than $$$1$$$ and can only be divided by $$$1$$$ and itself.

Walk Alone likes growing things, so he wants to use this magic to make this sequence non-decreasing. Besides, Walk Alone doesn't like negative numbers, so during the whole operations any number cannot be negative.

He wants to accomplish this idea with minimal number of magic usage. Although Walk Alone has this magic, he doesn't know in which order to use it, so he asks you for help.

Input

There are $$$T$$$ test cases you need to answer.

First line of the whole input contains a single integer $$$T$$$ ($$$1 \le T \le 100$$$) denoting the number of test cases.

For each test case, the first line contains one integer $$$n$$$ $$$(10\leq n\leq 2\times 10^3)$$$, denoting the length of the sequence.

The following line contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ ($$$1\leq a_i \leq 10^5$$$), denoting the sequence.

It's guaranteed that in all test cases, $$$\sum n \le 2\times 10^4$$$.

Output

For each test case, output a single integer in a line denoting the minimum number of magic usage to accomplish the task.

Example
Input
4
10
1 10 8 2 3 4 1 2 1 8
12
29 31 2 1 34 29 31 24 18 2 9 10
10
1 2 3 4 5 6 7 8 9 10
10
2 2 1 1 2 2 1 1 2 2
Output
12
96
0
4