Ống Nghiệm

Bessie có hai ống nghiệm, mỗi ống chứa $N$ đơn vị chất lỏng gồm hai màu là màu 1 và màu 2. Chất lỏng trong một bình xếp thành các lớp, mỗi lớp là một nhóm nhiều nhất có thể các đơn vị cùng màu nằm liền nhau. Bessie còn một chiếc cốc rỗng để hỗ trợ. Cả ba bình đều có sức chứa không giới hạn.

Một lần rót từ bình $a$ sang bình $b$ lấy toàn bộ lớp trên cùng của $a$ và đổ sang $b$. Lần rót chỉ hợp lệ khi $a$ không rỗng, và $b$ rỗng hoặc màu ở đỉnh $b$ trùng với màu của lớp được rót.

Bessie muốn cuối cùng mỗi ống nghiệm chỉ còn một màu (hai ống mang hai màu khác nhau) và chiếc cốc rỗng. Gọi $M$ là số lần rót ít nhất để làm được điều đó.

Dữ liệu vào

• Dòng 1: số nguyên $T$, số lượng test case.
• Với mỗi test case:
  • Dòng 1: hai số nguyên $N$ và $P$.
  • Dòng 2: xâu $N$ ký tự gồm '1' và '2' mô tả ống nghiệm 1 từ đáy lên đỉnh.
  • Dòng 3: xâu tương tự mô tả ống nghiệm 2.

Dữ liệu ra

Với mỗi test case, $P$ quyết định dạng kết quả:

• $P=1$: in một dòng chứa $M$.
• $P=2$: in số nguyên $A$ với $M\le A\le M+5$, rồi $A$ dòng mô tả các lần rót.
• $P=3$: in $M$, rồi đúng $M$ dòng mô tả các lần rót.

Mỗi lần rót ghi trên một dòng hai số nguyên là bình nguồn và bình đích, trong đó 1 là ống nghiệm 1, 2 là ống nghiệm 2 và 3 là chiếc cốc. Mọi lần rót phải hợp lệ, và sau lần rót cuối cùng mỗi ống nghiệm chỉ còn một màu còn chiếc cốc rỗng.

Nếu có nhiều dãy lần rót thoả mãn, in ra một dãy bất kỳ.

Ràng buộc

• $1\le T\le 10$
• $1\le N\le {10}^5$
• $1\le P\le 3$
• Mỗi màu xuất hiện ít nhất một lần trong dữ liệu vào của mỗi test case.

Ví dụ