Задачі
Судоку
Судоку
\includegraphics{https://static.e-olymp.com/content/d2/d2fd1cca6533f4850588740d4592dde1dd51dd65.jpg}
О, ні! Білл просто зрозумів, что ця Судоку, над розв'язанням якої він провів останні десять хвилин, по суті, була задачею з минулого тижня, лише повернутою проти годинникової стрілки. Як дешево! Невже журнал не може дозволити собі нову задачу кожного тижня? Звичайно, він не мав можливості взнати про це до того, як почав її розв'язувати, да й порожні місця для заповнення цифрами були іншими, ніж минулого тижня. Тим не менше, розуміння того, что на цьому тижні ломиголовка була простою похідною від задачі з минулого тижня, звичайно, принесло задоволення більше, ніж розв'язання усього іншого.
Поле для Судоку складається з таблиці \textbf{9}×\textbf{9 }клітинок. Вони можут бути згруповані у \textbf{3}×\textbf{3} областях розміром \textbf{3}×\textbf{3 }клітинки кожна. Деякі клітинки заповнено цифрами від \textbf{1} до \textbf{9}, а інші залишаються порожніми. Мета гри полягає у тому, щоб заповнити кожну порожню клітинку цифрою \textbf{1...9} так, щоб у кожному рядку, кожному стовбці і у кожній області містилась кожна з цифр \textbf{1...9} лише один раз. Правильне судоку завжди має рівно один розв'язок.
Допоможіть Біллу уникнути неприємних сюрпризів, написавши програму, яка перевірить, чи є нерозв'язані Судоку дійсно похідними від більш ранніх задач, отримані при допомозі простих операцій.
Дозволеними операціями є:
\begin{enumerate}
\item Поворот усієї ломиголовки за годинниковою стрілкою або проти годинникової стрілки.
\item Обмін двох стовбців у колонці розміром \textbf{3}×\textbf{9} у одному сегменті.
\item Обмін двох рядків у смузі розміром \textbf{9}×\textbf{3 }у одному сегменті.
\item Обмін місцями сегментів рядків та стовбців.
\item Застосування перестановки \textbf{f} цифр \textbf{1...9} у кожній клітинці (наприклад, заміна \textbf{х} на \textbf{f(x)} у кожній клітинці).
\end{enumerate}
Вважається, що операція виконується над розв'язаним Судоку (а не над нерозв'язаними задачами), також завжди гарантиується, що якщо існував розв'язок до перетворення Судоку, то він існує і після нього.
\InputFile
Вхідні дані починаються з рядка, який містить кількість тестів \textbf{0} ≤ \textbf{N} ≤ \textbf{50}.
Далі для кожного тесту йде дев'ять рядків з описом розв'язання ломиголовки з минулого тижня, по рядках зверху до низу. Кожен рядок відповідає рядку у ломиголовці і складається з дев'яти цифр (\textbf{1...9}), які описують вміст комірок зліва праворуч.
Після розв'язку з минулого тижня йдуть блоки по дев'ять рядків з описом нерозв'язаних задач на цьому тижні. Тут, крім того, що кожен рядок відповідає рядкам ломиголовки і кожна цифра (\textbf{0...9}) описує вміст комірки, цифра \textbf{0} означає, що комірка порожня. Рядки подано по порядку зверху до низу, по одному у рядку, комірки впорядковано зліва праворуч.
Після кожного тесту, крім останнього йде порожній рядок. Кожна нерозв'язана ломиголовка гарантовано буде однозначно розв'язною, як і розв'язок з минулого тижня, і це завжди буде правильний розв'язок Судоку.
\OutputFile
Для кожного тесту виведіть \textbf{Yes}, якщо Судоку може бути отримано із заданого розв'язку ломиголовки з використанням дозволених операцій, або \textbf{No}, якщо це неможливо.
Вхідні дані #1
2 963174258 178325649 254689731 821437596 496852317 735961824 589713462 317246985 642598173 060104050 200000001 008305600 800407006 006000300 700901004 500000002 040508070 007206900 534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179 010900605 025060070 870000902 702050043 000204000 490010508 107000056 040080210 208001090
Вихідні дані #1
Yes No