시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2 2 2 100.000%

문제

The floating mountains of Pandora present a challenge for the human scientists, especially geologists and physicists, who have been trying to understand how such structures could exist. While exploring the mountains, the scientists stumbled across interesting stacked floating mountain structures, where different mountains appeared stacked above one other, with the larger mountains being higher up in the stack. The scientists were able to calculate the size of each mountain, and they made an interesting observation: that the sizes of the mountains formed a (generalized) Fibbonacci sequence.

A sequence of numbers: x1, x2, ..., xn, is called a generalized Fibbonacci sequence if, for all i > 2,

xi = xi−1 + xi−2

The standard Fibbonacci sequence is simply a generalized Fibbonacci sequence with x1 = x2 = 1.

An example of generalized Fibbonacci sequence is: 2, 5, 7, 12, 19, ...

Your goal is to help the scientists verify this conjecture. Specifically, you are to write a program that, given a sequence of numbers, decides whether the sequence is a generalized Fibbonacci sequence or not.

입력

The first line in the test data file contains the number of test cases, n. After that, each line contains one test case. The test case begins with the number of elements in the sequence, k, and then we have k numbers which form the sequence. Assume all numbers are ≥ 0, and that the numbers are all < 230.

출력

For each test case, you are to output “YES” (if the sequence is a generalized Fibbonacci sequence) or “NO” (if it is not).

예제 입력 1

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

예제 출력 1

YES
NO
YES