쌓인 부유 산

면접 대비

시간 제한1초메모리 제한128 MB

요약

여러 수열이 주어질 때 각 수열에서 세 번째 원소부터 바로 앞 두 원소의 합인지 판별한다.

난이도: 쉬움10점 중 2점
유형: 구현, 배열, 수학
정답자: 아직 제출이 없습니다

문제

판도라의 부유하는 산들은 인간 과학자들, 특히 이런 구조가 어떻게 존재할 수 있는지 이해하려는 지질학자와 물리학자들에게 커다란 수수께끼입니다. 산을 탐사하던 중, 과학자들은 흥미로운 "쌓인 부유 산" 구조를 발견했습니다. 서로 다른 산들이 위아래로 겹겹이 쌓여 있었고, 더 큰 산일수록 더 위쪽에 놓여 있었습니다. 과학자들은 각 산의 크기를 측정할 수 있었고, 그 크기들이 (일반화된) 피보나치 수열을 이룬다는 흥미로운 사실을 관찰했습니다.

수열 $x_1, x_2, \dots, x_n$ 이 모든 $i > 2$ 에 대해 다음을 만족하면, 이 수열을 일반화된 피보나치 수열이라고 부릅니다.

$x_i = x_{i-1} + x_{i-2}$

표준 피보나치 수열은 $x_1 = x_2 = 1$ 인 일반화된 피보나치 수열의 한 예입니다. 일반화된 피보나치 수열의 또 다른 예로는 $2, 5, 7, 12, 19, \dots$ 가 있습니다.

여러분의 목표는 이 관찰이 옳은지 검증하는 것입니다. 구체적으로, 주어진 수열이 일반화된 피보나치 수열인지 아닌지를 판정하는 프로그램을 작성하세요.

입력

첫째 줄에 테스트 케이스의 개수 $n$ 이 주어집니다. 이어지는 각 줄에는 하나의 테스트 케이스가 주어집니다. 각 테스트 케이스는 수열의 원소 개수 $k$ 로 시작하고, 그 뒤에 수열을 이루는 $k$ 개의 수가 차례로 주어집니다. 모든 수는 $0$ 이상이고 $2^{30}$ 미만입니다.

출력

각 테스트 케이스마다, 수열이 일반화된 피보나치 수열이면 YES 를, 그렇지 않으면 NO 를 한 줄에 하나씩 출력하세요.

예제1

예제 1

입력

3
6 1 1 2 3 5 8
7 1 2 2 4 6 10 16
4 2 10 12 22

예상 출력

YES
NO
YES