IQ 테스트

IQ 테스트에는 이런 유형이 자주 나온다.

정수 수열의 앞부분 몇 개가 주어졌을 때, 그다음 수는 무엇인가?

예를 들어 (1, 2, 3, 5, 8, 13, 21)이 주어지면 피보나치 수열이므로 다음 수가 34라는 것을 금방 알 수 있다.

다음 수는 정수지만 주어진 앞부분을 그대로 지나는 다항식이 아주 많고, 그래서 답 후보도 아주 많다. 이 문제에서는 아래 형태의 점화식을 만족하는 수열만 올바르다고 본다.

$f(n) = a_1 f(n-1) + a_2 f(n-2) + \cdots + a_d f(n-d)$

여기서 $1 \le d \le 3$이고 $a_1, \dots, a_d$는 정수다. 수열을 만족하는 식이 여러 개면 $d$가 가장 작은 식이 답이다.

입력은 여러 테스트 케이스로 이루어진다. 첫째 줄에 테스트 케이스의 수가 주어지며, 500을 넘지 않는다.

각 테스트 케이스는 한 줄이다. 줄의 첫 번째 수는 수열의 길이 $n$ ($8 \le n \le 12$)이고, 이어서 수열을 이루는 정수 $n$개가 공백으로 구분되어 주어진다. 각 정수의 절댓값은 1000을 넘지 않는다. 위 형태의 식을 적어도 하나 만족하는 수열만 주어지며, 답이 되는 식의 $d$에 대해 처음 $d$개 수는 0이 아니다.

각 테스트 케이스마다 다음 수를 한 줄에 하나씩 출력한다. 다음 수의 절댓값은 100,000을 넘지 않는다.