Tree

There are N (2<=N<=600) cities,each has a value of happiness,we consider two cities A and B whose value of happiness are VA and VB,if VA is a prime number,or VB is a prime number or (VA+VB) is a prime number,then they can be connected.What's more,the cost to connecte two cities is Min(Min(VA , VB),|VA-VB|).
Now we want to connecte all the cities together,and make the cost minimal.

The first will contain a integer t,followed by t cases.
Each case begin with a integer N,then N integer Vi(0<=Vi<=1000000).

If the all cities can be connected together,output the minimal cost,otherwise output "-1";

2
5
1
2
3
4
5

4
4
4
4
4

4
-1

Teddy

2009浙江大学计算机研考复试（机试部分）——全真模拟