English

After opening the door with Fingerprint authentication, Lam entered a room full of computers and servers with terrible configuration.

Lam started accessing the network here and this challenge is not small. The login screen to the system appeared and asked to enter the authentication code, after a wrong input, the system forced Lam to verify that he was not a robot.

The screen in front of Lam showed a very confusing string of characters: 1->5, 1->9, 7->4, ... and a picture like the phone's launcher interface (size 5×5), but the icons on the launcher interface are replaced with numbers from 1 to 25 as shown below.

After thinking about it for a while, Lam knew that this is just a way that the authentication system is not a robot, the sequence of numbers after performing operations such as the given sequence of characters may be a password to be used anywhere. that later.

For example, the character string is given as 1->5, 1->9, 7->4 through the transformation process, the original 5×5 matrix will give the result as described below.

Details of the move:

In order not to spend too much time on manual calculation, Lam sent this data to you and asked for your help to find the Password as quickly as possible. Please help Lam so he can quickly access the system.

Input

The first line describes the number of test cases T of the problem (T <= 100).

The first line of each test case is a natural number N (3 <= N<= 20) indicating the number of changes on the matrix that you need to make.

Followed by 5 lines, each line 5 characters from 1 to 25 indicates the value at position a[i][j].

Next N lines, each line contains 2 integers X, Y indicating the position to move from X to Y

Output

Each test case is printed on 6 lines with the following format:

• Start with the string "Case #", followed by the ordinal number of the test case, followed by a space, and finally the character ':'
• Next 5 lines, each line 5 integers. The result of the problem is a 5×5 matrix after performing the transformations.

Example

Input:
1
3
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
1 5
1 9
7 4

Output:
Case #1:
3 4 5 8 1
6 7 9 2 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

Vietnamese

Sau khi mở được cánh cửa có xác thực Vân tay, Lâm bước vào căn phòng với đầy dãy những chiếc máy tính, máy chủ cấu hình khủng.

Lâm bắt đầu truy cập vào hệ thống mạng tại đây và thử thách lần này là không nhỏ. Màn hình đăng nhập vào hệ thống hiện ra và yêu cầu nhập mã xác thực, sau một hồi nhập sai thì hệ thống đã bắt Lâm phải xác thực không phải là người máy (robot). 

Màn hình trước mặt Lâm hiện ra các chuỗi ký tự rât khó hiểu: 1->5, 1->9, 7->4, ... và một bức ảnh giống như giao diện Launcher của điện thoại (kích thước 5*5), có điểu các icon trên giao diện Launcher được thay bằng các số từ 1->25 như hình bên dưới.

Sau một hồi suy nghĩ thì Lâm biết rằng đây chỉ là cách mà hệ thống xác thực không phải người máy, dãy số sau khi thực hiệ các thao tác như dãy ký tự được cho có thể sẽ là một mật khẩu được sử dụng ở đâu đó sau này. 

Ví dụ chuỗi ký tự được cho là 1->5, 1->9, 7->4 qua quá trình biến đổi, ma trận 5*5 ban đầu sẽ cho kết quả như mô tả bên dưới.

Chi tiết bước di chuyển: 

Để không mất quá nhiều thời gian cho việc tính toán bằng tay, Lâm đã gửi dữ liệu này cho bạn và nhờ bạn giúp đỡ để tìm ra Mật khẩu một cách nhanh nhất. Bạn hãy giúp Lâm để anh ấy có thể nhanh chóng truy cập được vào hệ thống nhé.

Input

Dòng đầu tiên mô tả số lượng Testcase T của bài toán (T <= 100)

Dòng đầu tiên của mỗi testcase là số tự nhiên N (3 <= N<= 20) cho biết số lượng các thay đổi trên ma trận mà bạn cần phải thực hiện

Tiếp theo là 5 dòng, mỗi dòng 5 ký tự từ 1->25 cho biết giá trị tại vị trí a[i][j].

N dòng tiếp theo, mỗi dòng chứa 2 số nguyên X, Y cho biết vị trí cần dịch chuyển từ X->Y

Output

Mỗi testcase được in trên 6 dòng với định dạng sau:

 - Bắt đầu bằng chuỗi "Case #", tiếp theo là số thứ tự của testcase, theo sau là 1 dấu cách (khoảng trắng), và cuối cùng là ký tự ':'

 - 5 dòng tiếp theo, mỗi dòng 5 số nguyên. Kết quả bài toán là ma trận 5*5 sau khi thực hiện các phép biến đổi.

Example

Input:
1
3
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
1 5
1 9
7 4

Output:
Case #1:
3 4 5 8 1
6 7 9 2 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25