Beautiful Landscape

Doyoung likes to play with stacks of blocks. He treats each stack as a mountain and builds his own terrain out of them.

The stacks all stand in one row, and Doyoung moves a single block at a time. One move takes the top block of one of two neighbouring stacks and puts it on the other stack. Doyoung always rearranges his blocks this way.

A stack that holds at least one block is a mountain. The distance between two mountains is the difference of their positions in the row. A terrain is a beautiful landscape when every pair of mountains sits at a prime distance, and pairs that are not neighbours count too. A terrain with a single mountain is a beautiful landscape as well.

Suppose the stacks hold 1, 2, 1, 3, 2, 1, 2, 1 blocks from left to right. Leaving only two mountains costs at least 12 moves. Making stacks 2, 4 and 7 the mountains gives a beautiful landscape after 6 moves, because the distances 2, 3 and 5 between them are all prime.

Given the current blocks, find the smallest number of moves Doyoung needs to build a beautiful landscape.

The input holds several test cases.

The first line of each test case has the number of stacks $n$ ($1 \le n \le 30000$). The next line has $n$ integers $b$ ($0 \le b \le 1000$), the number of blocks on each stack from left to right. One space separates two integers, and the line has no leading or trailing space. A stack with no blocks is written as 0 too.

The last line of the input holds a single 0. That line is not a test case, it marks the end of the input.

For each test case, print the smallest number of moves needed to build a beautiful landscape, one answer per line. Print no other whitespace and no blank line.