题目描述

In a two dimensional array of integers of size $2 \times n$, is it possible to rearrange integers so that the sum of two adjacent elements (which are adjacent in a common row or a common column) is never divisible by three?

输入格式

The input has several test cases and the first line contains an integer $t (1 \le t \le 200)$ which is the number of test cases.

In each case, the first line contains an integer $n (1 \le n \le 10000)$ indicating the number of columns in the array. The second line contains the elements of the array in the first row separated by single spaces. The third line contains the elements of the array in the second row separated by single spaces. The elements will be positive integers less than $1000000$.

输出格式

For each test case, output “YES” in a single line if any valid rearrangement exists, or “NO” if not.

6
3
3 6 9
1 4 7
3
3 6 9
1 3 8
5
1 2 3 4 5
6 7 8 9 10
10
1 1 1 1 1 1 1 1 1 1
2 3 2 3 2 3 2 3 2 3  
2
3 1
2 3
2
3 1
1 2

YES
NO
YES
YES
YES
NO