This page is still under construction.

Parts of this page are still being built. What you see may change.

Game

Interview

Time limit2sMemory limit256 MB

Summary
Given an n by n grid of numbers where 0 marks an empty cell, decide whether the grid is good: it has an empty cell or two side-adjacent cells with equal values.
Level

Easy2 of 10

Topics
Implementation, Matrix, Brute force
Solved
No attempts yet

Problem

This problem mentions the game 2048, which has been popular recently. Knowing its rules is not required to solve the problem.

In his free time, Vasya likes to play the popular game 2048. After he figured out the right strategy, the game bored him, and he decided to make a similar game with his own rules.

The playing field in Vasya's game is a square of size n×nn \times n, with numbers written in some of its cells. We call a playing field good if the field has an empty cell, or if there are two cells sharing a side that contain equal numbers.

Given a playing field, determine whether it is good.

Input

The input contains several test cases. The first line contains the number T, the number of test cases (1 ≤ T ≤ 100). The descriptions of the test cases follow in the format below.

The first line of a description contains a single positive integer n (1 ≤ n ≤ 10), the size of the playing field. The next n lines contain n nonnegative integers each, the description of the playing field. An empty cell is given by the number 0, and a filled cell is given by the positive integer written in it, from 1 to 1000.

Output

Print T lines. For each test case, print "YES" if the field is good, or "NO" otherwise.

Examples1

  1. Example 1

    Input
    3
3 
1 2 3
3 1 2
0 2 1
3
1 2 3
4 5 6
7 8 9
3
1 2 3
4 5 6
7 5 9
    Expected output
    YES
NO
YES