Проблема Простих Чисел
Одним із найбільших викликів для викладача є складання питань для підсумкового іспиту. Доктор Гавамнія, який викладає курс "Основи алгоритмів" в Ісфаганському університеті (UI), розробив цікаву алгоритмічну задачу для свого іспиту. Він прагне, щоб студенти застосували всі свої алгоритмічні знання для оптимального та ефективного розв'язання цієї задачі. Завдання полягає в наступному: є кільце, що складається з N кіл, пронумерованих від 1 до N, як показано на діаграмі. Вам надано N цілих чисел. Необхідно розмістити ці числа в кожному колі так, щоб сума чисел у трьох сусідніх колах була простим числом.
Кожен тестовий випадок може мати кілька рішень, і ваше завдання — знайти те, яке має мінімальну зважену суму. Зважена сума визначається як сума добутків кожного числа в колі на порядковий номер цього кола. Наприклад, зважена сума на діаграмі вище дорівнює 36 (і це також мінімум).
Вхідні дані
Перша строка введення містить одне ціле число, яке вказує кількість тестових випадків. Далі йде одна строка для кожного тестового випадку. Кожен тестовий випадок починається з одного цілого числа, N (3 ≤ N ≤ 15), яке є кількістю кіл. Наступні N цілих чисел — це числа, які потрібно розмістити в колах (усі між 1 і 100, включно).
Вихідні дані
Для кожного тестового випадку виведіть одну строку. Якщо немає способу побудувати кільце, слід вивести слово "неможливо", або ж одне ціле число, яке є мінімальною зваженою сумою.