A. Конфетное бинго
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Алисы есть волшебная доска. Доска описывается как сетка размером $$$n\times n$$$; на каждой плитке находится цветная конфета. Цвет конфеты в $$$i$$$-й строке и $$$j$$$-м столбце обозначается как $$$a_{i,j}$$$.

Боб хочет узнать, может ли он переставить плитки на доске так, чтобы ни одна строка или столбец не состояли из $$$n$$$ конфет одного цвета.

Ваша задача — определить, существует ли такая перестановка.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1\le n\le 100$$$), обозначающее размер доски.

Следующие $$$n$$$ строк содержат по $$$n$$$ целых чисел; в $$$i$$$-й строке $$$j$$$-е число — это $$$a_{i,j}$$$ ($$$1\le a_{i,j}\le n^2$$$), обозначающее цвет конфеты на доске.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$500$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если существует допустимая перестановка, и «NO», в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
3
3
1 2 3
3 1 4
4 1 2
3
1 1 1
2 3 4
1 4 3
3
1 1 1
1 1 1
1 1 2
Выходные данные
YES
YES
NO
Примечание

В первом наборе входных данных ни одна строка или столбец не состоит из всех конфет одного цвета; доску можно оставить как есть.

Во втором наборе входных данных первая строка состоит из всех конфет цвета $$$1$$$. Доску можно переставить, поменяв местами $$$a_{1,1}$$$ с $$$a_{2,1}$$$. После перестановки доска становится $$$$$$ \begin{matrix} 2 & 1 & 1 \\ 1 & 3 & 4 \\ 1 & 4 & 3 \end{matrix} $$$$$$ Теперь ни одна строка или столбец не состоит из всех конфет одного цвета.

В третьем наборе входных данных, независимо от того, как будет переставлена доска, всегда будет хотя бы одна строка или столбец, состоящие из всех конфет цвета $$$1$$$. Поэтому допустимой перестановки не существует.