对于整数数组 $$$a_1, a_2, \dots, a_n$$$,我们定义它 平等特征 为数组 $$$b_2, b_3, \dots, b_{n-1}$$$,其中,如果数组 $$$a$$$ 的第 $$$i$$$ 元素等于其两个邻居,则 $$$b_i = 1$$$;如果数组的第 $$$i$$$ 元素等于其两个邻居,则 $$$b_i = 0$$$ $$$a$$$ 不等于至少一个邻居。
例如,对于数组 $$$[1, 2, 2, 2, 3, 3, 4, 4, 4, 4]$$$,相等特征将为 $$$[0, 1, 0, 0, 0, 0, 1, 1]$$$。
给定数组 $$$b_2, b_3, \dots, b_{n-1}$$$。您的任务是确定是否存在这样一个数组 $$$a$$$ ,其给定数组具有相等特征。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例由两行组成:
- 第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 100$$$);
- 第二行包含 $$$n-2$$$ 整数 $$$b_2, b_3, \dots, b_{n-1}$$$ ($$$0 \le b_i \le 1$$$)。
输出
对于每个测试用例,输出 是 如果数组 $$$a$$$ 存在,或者 NO 如果这样的数组不存在。每个字母都可以在任何情况下打印。
示例
输入复制
3100 1 0 0 0 0 1 131100 1 0 1 1 0 0 1
输出复制
YES YES NO
注意
在第一个示例中,数组 $$$a = [1, 2, 2, 2, 3, 3, 4, 4, 4, 4]$$$ 是合适的。
在第二个示例中,数组 $$$a = [7, 7, 7]$$$ 是合适的。