Тест 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.