Bài tập

Cho bàn cờ \(N \times N\). Một số quân hậu đã được đặt sẵn. Hãy đặt thêm các quân hậu còn lại để mỗi hàng và mỗi cột có đúng một quân hậu, đồng thời không có hai quân hậu nào tấn công nhau. Nếu không thể, in ra "NO".

\InputFile
Dòng đầu chứa số nguyên \(N\) (\(1 \le N \le 20\))

Tiếp theo là \(N\) dòng, mỗi dòng là một xâu dài \(N\) ký tự, mỗi ký tự là . (ô trống) hoặc Q (một quân hậu đã đặt sẵn).

\OutputFile
Nếu không có lời giải, in ra NO.

Ngược lại, in ra YES ở dòng đầu, sau đó in \(N\) dòng mô tả một cấu hình hợp lệ ở cùng định dạng đầu vào (dùng . và Q).

Example

4
..Q.
....
....
....

YES
..Q.
Q...
...Q
.Q..

Bạn được cho 2 số nguyên \(a, b\).

Hãy làm việc này sau đây cho đến khi một trong hai số \(a, b\) là số 0 :

• Nếu \(b \leq a\) thì lấy a trừ đi b \((a = a - b)\).
• ngươc lại lấy b trừ a\((b = b - a)\).

Nhập vào 2 số \(a, b\). Hãy đếm số lần bạn làm công việc trên

Input

• \(t (t \leq 1000)\) - số test

• \(t\) dòng, mỗi dòng gồm 2 số nguyên dương \(a, b (a, b \leq 1000000000)\)

Output

• \(t\) dòng, số lần thực hiện để một trong 2 số \(a, b\) có 1 số là số 0

Example

1
4 17

8

\begincenter

\endcenter

Example

5 2
3 1 2 3
2 2 4

34

Để trang trí cho tờ giấy vở hình chữ nhật kẻ ô vuông đơn vị (centimeter) dùng để viết thư cho bạn, An đánh dấu tích vào các ô xung quanh theo biên của tờ giấy.

Yêu cầu: Biết kích thước tờ giấy là \(m \times n\), hỏi An đánh dấu tích vào bao nhiêu ô?

Input

Vào từ tệp văn bản CAU1.INP :

Một dòng chứa hai số nguyên \(m, n\) cách nhau dấu cách \((1 \leq m, n \leq 10^8)\).

Output

Ghi ra tệp văn bản CAU1.OUT:

Gồm một dòng ghi một số là số ô An đánh dấu tích.

Example

4 5

14

v & v & v & v & v