B. Li Hua и узор
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Li Hua есть узор размером $$$n\times n$$$, каждая клетка которого либо синяя, либо красная. Он может выполнить ровно $$$k$$$ операций. За одну операцию он выбирает клетку и меняет ее цвет с красного на синий или с синего на красный. Каждая клетка может быть выбрана сколько угодно раз. Можно ли сделать узор, который соответствует его же повороту на $$$180^{\circ}$$$?

Предположим, что вы Li Hua. Пожалуйста, решите эту задачу.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n,k$$$ ($$$1\le n\le 10^3,0\le k \le 10^9$$$) — размер шаблона и количество операций.

Каждая из следующих $$$n$$$ строк содержит $$$n$$$ целых чисел $$$a_{i,j}$$$ ($$$a_{i,j}\in\{0,1\}$$$) — начальный цвет клетки: $$$0$$$ для синей и $$$1$$$ для красной.

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

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

Для каждого набора входных данных выведите «YES», если возможно получить узор, соответствующий его повороту на $$$180^{\circ}$$$, применив ровно $$$k$$$ операций, и «NO» в противном случае.

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

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

В первом наборе входных данных нельзя выполнить ни одной операции. Шаблон после вращения показан справа.

Во втором наборе входных данных можно выполнить операции над $$$(2,1),(3,2),(3,4)$$$. Шаблон после операций находится в середине, а шаблон после вращения — справа.