Тест на IQ
У багатьох тестах на IQ часто зустрічаються такі питання:
Дано перші кілька членів цілочислової послідовності, який наступний член?
Наприклад, якщо вам дана послідовність 1, 1, 2, 3, 5, 8, 13, 21, ви можете впізнати це як числа Фібоначчі і записати 34 як наступний член.
Немає "правильної відповіді", тому що наступний член може бути будь-яким цілим числом і все ще бути згенерованим поліномом (можливо, дуже високого ступеня). У цій задачі нас цікавлять лише послідовності, які задовольняють рекурентне співвідношення виду
f(n) = a_1f(n − 1) + ... + a_df(n − d),
де 1 ≤ d ≤ 3, і a_1, ..., a_d є цілими числами. Якщо послідовність задовольняє кілька рекурентних співвідношень вищезгаданого типу, ми завжди віддаємо перевагу тому, у якого менше d.
Вхідні дані
Вхід складається з кількох тестових випадків. Перша строка входу - це одне ціле число, не більше 500, що вказує кількість тестових випадків, які слідують. Кожен випадок задається в одному рядку. Кожен рядок містить кілька цілих чисел: кількість даних членів послідовності n (8 ≤ n ≤ 12), за якими слідують n цілих чисел, що містять дану послідовність. Кожен з даних членів має абсолютні значення не більше 1000. Ви також можете припустити, що дана послідовність задовольняє принаймні одне рекурентне співвідношення у вищезгаданій формі. Перші d членів у даній послідовності є ненульовими, для найменшого d, для якого існує рекурентне співвідношення.
Вихідні дані
Для кожного випадку виведіть у рядку наступний член, згенерований рекурентним співвідношенням, вибраним за вищезгаданими критеріями. Ви можете припустити, що наступний член у послідовності має абсолютне значення не більше 100000.