시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 89 23 21 25.000%

문제

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을 넘지 않는다.

예제 입력 1

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

예제 출력 1

34
1
256
W3sicHJvYmxlbV9pZCI6IjkzMzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJJUSBcdWQxNGNcdWMyYTRcdWQyYjgiLCJkZXNjcmlwdGlvbiI6IjxwPklRIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWM3MjBcdWQ2MTVcdWM3NzQgXHVjOGZjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjA5Y1x1YjJlNC48XC9wPlxyXG5cclxuPGJsb2NrcXVvdGU+XHVjODE1XHVjMjE4IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWNjOThcdWM3NGMgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViMmU0XHVjNzRjIFx1YzIxOFx1YjI5NCBcdWJiMzRcdWM1YzdcdWM3N2NcdWFlNGM/PFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzIxOFx1YzVmNCAoMSwgMiwgMywgNSwgOCwgMTMsIDIxKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHVjMjE4XHVjNWY0XHVjNzQwIFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWM1ZjRcdWM3NzRcdWFjZTAgXHViMmU0XHVjNzRjIFx1YzIxOFx1YjI5NCAzNFx1Yjc3Y1x1YjI5NCBcdWFjODNcdWM3NDQgXHVjMjdkXHVhYzhjIFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXHVjMjE4XHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YzljMFx1YjljYywgXHViYjM4XHVjODFjXHVjNzU4IFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViOWU0XHVjNmIwIFx1YjljZVx1Yzc0MCBcdWIyZTRcdWQ1NmRcdWMyZGRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM4MTVcdWIyZjVcdWM3NzQgXHViOWU0XHVjNmIwIFx1YzVlY1x1YjdlYyBcdWFjMWMgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWNcdWIyOTQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQ2MTVcdWQwZGNcdWM3NTggXHVjMmRkXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWMyMThcdWM1ZjRcdWI5Y2MgXHVjNjJjXHViYzE0XHViOTc0XHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+ZihuKSA9IGE8c3ViPjE8XC9zdWI+ZihuICZtaW51czsgMSkgKyAuIC4gLiBhPHN1Yj5kPFwvc3ViPmYobiAmbWludXM7IGQpLDxcL3A+XHJcblxyXG48cD4xICZsZTsgZCAmbGU7IDMgXHVjNzc0XHVhY2UwLCBhPHN1Yj4xPFwvc3ViPiwgLi4uLCBhPHN1Yj5kPFwvc3ViPlx1YjI5NCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuIFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjMmRkXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMWMgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBkXHVhYzAwIFx1Yzc5MVx1Yzc0MCBcdWFjODNcdWM3NzQgXHVjODE1XHViMmY1XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgNTAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YWUzOFx1Yzc3NCBuICg4ICZsZTsgbiAmbGU7IDEyKSBcdWM3NzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBuXHVhYzFjIFx1YzIxOFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NTggXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YmE3MCwgXHVjODA4XHViMzEzXHVhYzEyXHVjNzc0IDEwMDBcdWM3NDQgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVkNTZkXHVjMGMxIFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NThcdWIwOThcdWM3NTggXHVjMmRkXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWMyMThcdWM1ZjRcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWNjOThcdWM3NGMgZFx1YWMxYyBcdWMyMmJcdWM3OTBcdWIyOTQgMFx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViOWM4XHViMmU0IFx1YjJlNFx1Yzc0YyBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjMjE4XHVjNzU4IFx1YzgwOFx1YjMxM1x1YWMxMlx1Yzc0MCAxMDAsMDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTMzNCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IklRIFRlc3QiLCJkZXNjcmlwdGlvbiI6IjxwPkluIG1hbnkgSVEgdGVzdHMsIHRoZSBmb2xsb3dpbmcgdHlwZSBvZiBxdWVzdGlvbnMgaXMgb2Z0ZW4gZ2l2ZW46PFwvcD5cclxuXHJcbjxibG9ja3F1b3RlPkdpdmVuIHRoZSBcdWZiMDFyc3QgZmV3IHRlcm1zIG9mIGFuIGludGVnZXIgc2VxdWVuY2UsIHdoYXQgaXMgdGhlIG5leHQgdGVybT88XC9ibG9ja3F1b3RlPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGlmIHlvdSBhcmUgZ2l2ZW4gdGhlIHNlcXVlbmNlIDEsIDEsIDIsIDMsIDUsIDgsIDEzLCAyMSB5b3UgbWF5IHJlY29nbml6ZSB0aGlzIGFzIHRoZSBGaWJvbmFjY2kgbnVtYmVycyBhbmQgd3JpdGUgZG93biAzNCBhcyB0aGUgbmV4dCB0ZXJtLjxcL3A+XHJcblxyXG48cD5UaGVyZSBpcyBubyAmbGRxdW87Y29ycmVjdCBhbnN3ZXImcmRxdW87IGJlY2F1c2UgdGhlIG5leHQgdGVybSBjYW4gYmUgYW55IGludGVnZXIgYW5kIHN0aWxsIGJlIGdlbmVyYXRlZCBieSBhIHBvbHlub21pYWwgKHBvc3NpYmx5IG9mIGEgdmVyeSBoaWdoIGRlZ3JlZSkuIEluIHRoaXMgcHJvYmxlbSwgd2UgYXJlIG9ubHkgaW50ZXJlc3RlZCBpbiBzZXF1ZW5jZXMgdGhhdCBzYXRpc2Z5IGEgcmVjdXJyZW5jZSByZWxhdGlvbiBvZiB0aGUgZm9ybTxcL3A+XHJcblxyXG48cD5mKG4pID0gYTxzdWI+MTxcL3N1Yj5mKG4gJm1pbnVzOyAxKSArIC4gLiAuIGE8c3ViPmQ8XC9zdWI+ZihuICZtaW51czsgZCksPFwvcD5cclxuXHJcbjxwPndoZXJlIDEgJmxlOyBkICZsZTsgMywgYW5kIGE8c3ViPjE8XC9zdWI+LCAuLi4gLCBhPHN1Yj5kPFwvc3ViPiBhcmUgaW50ZWdlcnMuIElmIHRoZSBzZXF1ZW5jZSBzYXRpc1x1ZmIwMWVzIG11bHRpcGxlIHJlY3VycmVuY2UgcmVsYXRpb25zIG9mIHRoZSB0eXBlIGFib3ZlLCB3ZSB3aWxsIGFsd2F5cyBwcmVmZXIgb25lIHdpdGggYSBzbWFsbGVyIGQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIG11bHRpcGxlIHRlc3QgY2FzZXMuIFRoZSBcdWZiMDFyc3QgbGluZSBvZiBpbnB1dCBpcyBhIHNpbmdsZSBpbnRlZ2VyLCBub3QgbW9yZSB0aGFuIDUwMCwgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgdG8gZm9sbG93LiBFYWNoIGNhc2UgaXMgc3BlY2lcdWZiMDFlZCBvbiBvbmUgbGluZS4gRWFjaCBsaW5lIGNvbnRhaW5zIGEgbnVtYmVyIG9mIGludGVnZXJzOiB0aGUgbnVtYmVyIG9mIGdpdmVuIHRlcm1zIGluIHRoZSBzZXF1ZW5jZSBuICg4ICZsZTsgbiAmbGU7IDEyKSwgZm9sbG93ZWQgYnkgbiBpbnRlZ2VycyBjb250YWluaW5nIHRoZSBnaXZlbiBzZXF1ZW5jZS4gRWFjaCBvZiB0aGUgZ2l2ZW4gdGVybXMgaGFzIGFic29sdXRlIHZhbHVlcyBhdCBtb3N0IDEwMDAuIFlvdSBtYXkgYWxzbyBhc3N1bWUgdGhhdCB0aGUgZ2l2ZW4gc2VxdWVuY2Ugc2F0aXNcdWZiMDFlcyBhdCBsZWFzdCBvbmUgcmVjdXJyZW5jZSByZWxhdGlvbiBpbiB0aGUgZm9ybSBkZXNjcmliZWQgYWJvdmUuIFRoZSBcdWZiMDFyc3QgZCB0ZXJtcyBpbiB0aGUgZ2l2ZW4gc2VxdWVuY2UgYXJlIG5vbi16ZXJvLCBmb3IgdGhlIHNtYWxsZXN0IGQgZm9yIHdoaWNoIGEgcmVjdXJyZW5jZSBleGlzdHMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggY2FzZSwgZGlzcGxheSBvbiBhIGxpbmUgdGhlIG5leHQgdGVybSBnZW5lcmF0ZWQgYnkgdGhlIHJlY3VycmVuY2UgcmVsYXRpb24gc2VsZWN0ZWQgYnkgdGhlIGNyaXRlcmlhIGFib3ZlLiBZb3UgbWF5IGFzc3VtZSB0aGF0IHRoZSBuZXh0IHRlcm0gaW4gdGhlIHNlcXVlbmNlIGhhcyBhYnNvbHV0ZSB2YWx1ZSBhdCBtb3N0IDEwMCwwMDAuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d