시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 82 21 19 23.750%

문제

IQ 테스트 문제에는 다음과 같은 유형이 주로 나타난다.

정수 수열의 처음 몇 개의 수가 주어졌을 때, 다음 수는 무엇일까?

예를 들어, 수열 (1, 2, 3, 5, 8, 13, 21)이 주어졌을 때, 이 수열은 피보나치 수열이고 다음 수는 34라는 것을 쉽게 알 수 있다.

다음 수는 정수이지만, 문제의 수열을 만족하는 매우 많은 다항식이 존재할 수 있기 때문에, 정답이 매우 여러 개 있을 수 있다. 이 문제에서는 다음과 같은 형태의 식을 만족하는 수열만 올바르다고 한다.

f(n) = a1f(n − 1) + . . . adf(n − d),

1 ≤ d ≤ 3 이고, a1, ..., ad는 정수이다. 수열을 만족하는 식이 여러 개 있는 경우에는 d가 작은 것이 정답이다.

입력

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

각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 숫자는 수열의 길이 n (8 ≤ n ≤ 12) 이다. 다음 n개 수는 수열의 들어있는 정수이며, 절대값이 1000을 넘지 않는다. 항상 적어도 하나의 식을 만족하는 수열만 주어지며, 처음 d개 숫자는 0이 아니다.

출력

각 테스트 케이스 마다 다음 수를 출력한다. 다음 수의 절대값은 100,000을 넘지 않는다.

예제 입력

3
8 1 1 2 3 5 8 13 21
8 1 1 1 1 1 1 1 1
8 1 -2 4 -8 16 -32 64 -128

예제 출력

34
1
256

힌트