Судоку

О, ні! Білл просто зрозумів, что ця Судоку, над розв'язанням якої він провів останні десять хвилин, по суті, була задачею з минулого тижня, лише повернутою проти годинникової стрілки. Як дешево! Невже журнал не може дозволити собі нову задачу кожного тижня? Звичайно, він не мав можливості взнати про це до того, як почав її розв'язувати, да й порожні місця для заповнення цифрами були іншими, ніж минулого тижня. Тим не менше, розуміння того, что на цьому тижні ломиголовка була простою похідною від задачі з минулого тижня, звичайно, принесло задоволення більше, ніж розв'язання усього іншого.

Поле для Судоку складається з таблиці 9×9 клітинок. Вони можут бути згруповані у 3×3 областях розміром 3×3 клітинки кожна. Деякі клітинки заповнено цифрами від 1 до 9, а інші залишаються порожніми. Мета гри полягає у тому, щоб заповнити кожну порожню клітинку цифрою 1...9 так, щоб у кожному рядку, кожному стовбці і у кожній області містилась кожна з цифр 1...9 лише один раз. Правильне судоку завжди має рівно один розв'язок.

Допоможіть Біллу уникнути неприємних сюрпризів, написавши програму, яка перевірить, чи є нерозв'язані Судоку дійсно похідними від більш ранніх задач, отримані при допомозі простих операцій.

Дозволеними операціями є:

1. Поворот усієї ломиголовки за годинниковою стрілкою або проти годинникової стрілки.

2. Обмін двох стовбців у колонці розміром 3×9 у одному сегменті.

3. Обмін двох рядків у смузі розміром 9×3 у одному сегменті.

4. Обмін місцями сегментів рядків та стовбців.

5. Застосування перестановки f цифр 1...9 у кожній клітинці (наприклад, заміна х на f(x) у кожній клітинці).

Вважається, що операція виконується над розв'язаним Судоку (а не над нерозв'язаними задачами), також завжди гарантиується, що якщо існував розв'язок до перетворення Судоку, то він існує і після нього.

Вхідні дані

Вхідні дані починаються з рядка, який містить кількість тестів 0 ≤ N ≤ 50.

Далі для кожного тесту йде дев'ять рядків з описом розв'язання ломиголовки з минулого тижня, по рядках зверху до низу. Кожен рядок відповідає рядку у ломиголовці і складається з дев'яти цифр (1...9), які описують вміст комірок зліва праворуч.

Після розв'язку з минулого тижня йдуть блоки по дев'ять рядків з описом нерозв'язаних задач на цьому тижні. Тут, крім того, що кожен рядок відповідає рядкам ломиголовки і кожна цифра (0...9) описує вміст комірки, цифра 0 означає, що комірка порожня. Рядки подано по порядку зверху до низу, по одному у рядку, комірки впорядковано зліва праворуч.

Після кожного тесту, крім останнього йде порожній рядок. Кожна нерозв'язана ломиголовка гарантовано буде однозначно розв'язною, як і розв'язок з минулого тижня, і це завжди буде правильний розв'язок Судоку.

Вихідні дані

Для кожного тесту виведіть Yes, якщо Судоку може бути отримано із заданого розв'язку ломиголовки з використанням дозволених операцій, або No, якщо це неможливо.

Приклади