出题人太菜，暂无测试数据。

题目描述

给定一个大小为 \( N \) 的非负整数集合 \( S = \{ A_1, A_2, \dots, A_N \} \)。

有一个变量 \( x \)，初始值为 \( x = A_1 \)。你可以任意多次进行以下操作：

1. 从集合 \( S \) 中选择一个元素 \( y \)。
2. 当 \( y \) 满足以下条件时，将 \( x \) 赋值为 \( y \)。

条件：当 \( x \) 和 \( y \) 都用三进制表示时，将 \( x \) 位权为 \( 3^j \) 位的数字记为 \( X_j \)，将 \( y \) 位权为 \( 3^j \) 位的数字记为 \( Y_j \)。要求满足 \( X_j > Y_j \) 的 \( j \) 的个数最多为1。

请你判断是否可以通过若干次操作使 \( x = S_N \)。

输入输出格式

输入格式

第一行一个正整数 \(T\) 表示测试数据组数。
每组测试数据第一行一个正整数 \(N\), 第二行 \(N\) 个非负整数 \(A_1,\cdots,A_N\).

输出格式

输出 \(T\) 行每行一个字符串 “yes” 或 “no” 表示是否可行。

样例

输入

3
2
12 1
2
21 14
5
5 15 45 135 405

输出

no
yes
yes

数据范围

对于 \(30\%\) 的数据, \(N\le 100\)

对于另外 \(30\%\) 的数据，\(N \le 1000\)

对于 \(100\%\) 的数据, \(2\le N \le 2\times 10^5, T\le 20,0\le S_i< 3^{12}, \sum N\le 5\times 10^5\)