Primes' Problem#94
One of the most challenging tasks for a teacher is preparing questions for a final exam. Dr. Ghavamnia, who teaches the course "Fundamentals of Algorithms" at the University of Isfahan (UI), has created an interesting algorithmic problem for his exam. He wants students to use all their algorithmic skills to solve this problem as efficiently as possible. The problem is as follows:
A ring consisting of circles, numbered from to , is given as shown in the diagram. You are given integers. Arrange these numbers in the circles so that the sum of the numbers in any three consecutive circles is a prime number.
Each test case may have several solutions. Your task is to find an arrangement with the minimum weighted sum. The weighted sum is calculated as follows: for each circle, multiply the number placed in it by its circle number and sum the results. For example, in the diagram above, the weighted sum is (and this is the minimum possible value).
The first line contains the number of test cases. Each of the following lines describes one test case. Each test case starts with an integer (3 \le N \le 15), the number of circles. Then integers follow — the numbers to be placed in the circles (each from to , inclusive).
For each test case, print one line. If it is impossible to arrange the numbers according to the requirements, print impossible. Otherwise, print the minimum weighted sum.
Example 1