25561번 - 1-3 트리

문제

윤화는 친구 형건이에게서 트리를 선물로 받았다. 이 트리에는 특징이 하나 있는데, 각각의 정점의 차수가 1ドル$ 또는 3ドル$이라는 것이다. 트리의 구조를 잘 기억하기 위해 윤화는 다음과 같은 방법을 쓰기로 했다.

• 트리에서 차수가 1ドル$ 이하인 정점을 모두 골라서 각각의 정점에 정수 1ドル$을 적는다. 그런 다음 고른 정점들 및 인접한 간선을 트리에서 제거한다.
• 트리에서 차수가 1ドル$ 이하인 정점을 모두 골라서 각각의 정점에 정수 2ドル$를 적는다. 그런 다음 고른 정점들 및 인접한 간선을 트리에서 제거한다.
• 트리에서 차수가 1ドル$ 이하인 정점을 모두 골라서 각각의 정점에 정수 3ドル$을 적는다. 그런 다음 고른 정점들 및 인접한 간선을 트리에서 제거한다.
• 정점이 모두 제거될 때까지 같은 과정을 반복한다. $i$번째 과정에서 제거되는 정점에 적히는 수는 $i$이며, 마지막으로 제거된 정점에 적히는 수는 $n$이다.
• 모든 정점이 제거되었다면, 1ドル$부터 $n$까지의 정수가 정점에 적힌 횟수 $c_1, c_2, \ldots, c_n$을 구한다.

안타깝게도 트리에 정점이 너무 많아서 윤화는 횟수를 제대로 셌는지 알 수 없었다. 윤화를 도와 주어진 값들이 유효한지 알려주자!

간선에 방향이 없는 트리에서 정점의 차수는 그 정점과 연결된 간선의 개수를 의미한다.

입력

첫째 줄에 테스트 케이스의 수 $T$가 입력된다. $(1 \le T \le 1,000円,000円)$

각각의 테스트 케이스는 두 줄로 이루어져 있다.

테스트 케이스의 첫째 줄에는 마지막으로 제거된 정점에 적힌 수 $n$이 입력된다. $(1 \le n \le 1,000円,000円)$

테스트 케이스의 둘째 줄에는 $n$개의 정수 $c_1, c_2, \ldots, c_n$이 공백으로 구분되어 입력된다. $(1 \le c_1, c_2, \ldots, c_n \le 10^9)$

입력 파일 하나에 존재하는 모든 테스트 케이스의 $n$의 합은 1ドル,000円,000円$을 넘지 않는다.

출력

각각의 테스트 케이스에 대해 주어진 값들로 복원할 수 있는 트리가 하나라도 존재한다면 YES, 아니면 NO를 한 줄에 하나씩 출력한다.

제한

노트