该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

八数码想必大家都玩过，现给定一个十五数码局面，判断是否有解。

Description

现有一个4*4的棋盘，上面不重复的放满了0~15中的数字。例如：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0
就是一个棋盘局面，事实上它就是初始局面的棋盘。
每次“操作”可以将0和他周围上下左右的四个数字交换，不能交换到棋盘外去，例如交换0和12棋盘局面变成
1 2 3 4
5 6 7 8
9 10 11 0
13 14 15 12
再交换0和11局面变成:
1 2 3 4
5 6 7 8
9 10 0 11
13 14 15 12

现在给定一个局面，试判断它是否能通过若干次“操作”之后复原成初始局面。

Format

Input

第一行一个正整数T，表示数据组数
对于接下来每组数据，共四行，每行四个正整数，即棋盘描述。

Output

共T行，对于每组数据，如果能复原成初始局面，该行输出“YES”，否则该行输出“NO”。

Sample 1

Input

2
1 2 3 4
5 6 7 8
9 10 11 0
13 14 15 12
2 1 3 4
5 6 7 8
9 10 11 12
0 13 14 15

Output

YES
NO

Limitation

1s, 128Mb for each test case.

Source

lyhlyhlyh