Tướng G được giao nhiệm vụ bảo vệ thành phố Alpha có dạng hình lục giác đều. Sau khi khảo sát địa thế và tìm chiến thuật để bảo vệ thành phố, Tướng G chia thành phố thành ~3n(n+1)+1~ khu vực có hình dạng ô tổ ong lục giác đều bằng nhau, phân bố đều xung quanh khu vực trung tâm. Các khu vực (các ô tổ ong) được đánh số ~1,2,3,\dots,3n(n+1)+1~ theo đường xoáy trôn ốc cùng chiều kim đồng hồ, bắt đầu từ khu vực trung tâm (xem minh họa với ~n=2~ ở hình ~1~). Một khu vực có thể có nhiều nhất ~6~ khu vực chung cạnh lân cận (xem minh họa ở hình ~2~). Tướng G đã cho đặt ~m~ bệ pháo giống hệt nhau ở ~m~ khu vực phân biệt có chỉ số ~p_1,p_2,\dots,p_m~ (~1 \leq p_1,p_2,\dots,p_m \leq 3n(n+1)+1~).

Tuy nhiên, sau khi nhận được những tin tức mới nhất từ quân báo về khả năng tấn công của địch, Tướng G quyết định thay đổi vị trí đặt các bệ pháo. Cụ thể, thay vì đặt các bệ pháo ở các khu vực ~p_1,p_2,\dots,p_m~, theo kế hoạch mới, chúng sẽ được đặt ở ~m~ khu vực phân biệt có chỉ số ~q_1,q_2,\dots,q_m~ (~1 \leq q_1,q_2,\dots,q_m \leq 3n(n+1)+1~). Để thực hiện việc di chuyển các bệ pháo sang các vị trí mới, Tướng G cần điều động các đội vận chuyển. Với mục đích giữ bí mật về các vị trí mới của các bệ pháo, mỗi đội vận chuyển được điều động chỉ thực hiện việc di chuyển bệ pháo từ một khu vực sang khu vực lân cận kề cạnh không có bệ pháo và sau khi hoàn thành nhiệm vụ này đội tự giải thể.

Cho biết danh sách ban đầu về các vị trí đặt các bệ pháo và danh sách mới về các vị trí đặt các bệ pháo, hãy giúp tướng G đưa ra phương án thực hiện việc di chuyển các bệ pháo đến các vị trí mới mà phải điều động ít đội vận chuyển nhất.

Input

Dòng thứ nhất gồm một số nguyên dương ~T~ ~(T\leq 5)~ là số lượng bộ dữ liệu. Mô tả của mỗi bộ dữ liệu như sau:

Dòng đầu tiên của mỗi bộ dữ liệu gồm một số nguyên dương ~n~ và ~m~ (~n\le 50~, ~m < 3n(n+1)+1~).

Dòng thứ hai của mỗi bộ dữ liệu gồm ~m~ số nguyên dương ~p_1,p_2,\dots,p_m~ (~1 \leq p_1,p_2,\dots,p_m \leq 3n(n+1)+1~).

Dòng thứ ba của mỗi bộ dữ liệu gồm ~m~ số nguyên dương ~q_1,q_2,\dots,q_m~ (~1 \leq q_1,q_2,\dots,q_m \leq 3n(n+1)+1~).

Output

Với mỗi bộ dữ liệu, in ra một nhóm dòng theo khuôn dạng sau:

• Dòng đầu tiên ghi ra số nguyên không âm ~s~ là số lượng đội cần điều động để thực hiện việc di chuyển các bệ pháo;

• Tiếp đến là ~s~ dòng mô tả nhiệm vụ của ~s~ đội. Mỗi dòng ghi ~2~ số nguyên ~u, v~ cách nhau bởi dấu cách cho biết cần thực hiện việc di chuyển bệ pháo từ khu vực ~u~ sang khu vực ~v~.

  Nếu có nhiều phương án thực hiện thì chỉ cần đưa ra một cách bất kì.

Scoring

Sample Input 1

1
2 3
7 2 3
2 1 5

Sample Output 1

3
7 1
1 5
3 1

Notes

Tướng G cần điều động ít nhất ~3~ đội vận chuyển. Việc di chuyển ~3~ bệ pháo được đặt ở ba khu vực ~7, 2, 3~ sang ba vị trí mới được tiến hành như sau:

• Bệ pháo ở khu vực ~2~ giữ nguyên vị trí;

• Điều động một đội vận chuyển để di chuyển bệ pháo ở khu vực ~7~ sang khu vực ~1~. Tiếp đến, điều động một đội vận chuyển khác để di chuyển bệ pháo này sang khu vực ~5~.

• Cuối cùng, điều động một đội vận chuyển nữa để di chuyển bệ pháo đặt ở khu vực ~3~ sang khu vực ~1~.

Tộng cộng, theo phương án này cần điều động ~3~ đội vận chuyển.