Is Peter’s birthday! And his friends are preparing a big party, however, Peter is obsessed with a variation of the famous game Minesweeper, moreover, Peter hates losing, so if any of you or your friends can beat him in the game, he will get angry and will attend the party that everyone is organizing for him.

This new mode of Minesweeper consists in building the gameboard given the mines, so, if the matrix has size of (2×2) and there is a mine in the position (0, 0) of the matrix, the resultant gameboard will be *1 11 Your task is to beat Peter and celebrate his birthday before its too late! Please have in consideration that:

• The cell (i, j) where there is a mine will be denoted as ’*’.
• The cell (i, j) where there is no mine will be denoted as ’-’.
• The cell (i, j) where there is N mines adjacent to it, will be denoted as a number from 1 to 8 (depending on the number of adjacencies.)

Input

The first line contains an integer T, which specifies the number of test cases. Then, will follow the descriptions of T test cases.

For each test case, you will have a line with three numbers N, M, K, denoting, respectively, the size of the matrix, formed by N columns and M rows, and K mines. Then, K lines will follow, each containing two numbers Ki and Kj denoting the position where the mine is in the board.

Output

For each test case you should print the string "Scenario #i:" where i represents the test case you are analyzing (starting from 1), then, in the next line, you shall print the gameboard as specified.

Example

Input:
3
3 2 2
0 0
1 1
3 3 3
0 0
1 1
2 2
8 8 10
0 1
5 0
2 5
4 5
2 6
5 6
6 6
5 7
6 7
7 7

Output:
Scenario #1:
*2
2*
11
Scenario #2:
*21
2*2
12*
Scenario #3:
1*1-----
111-1221
----1**1
----2331
11--1*32
*1--13**
11---2**
-----13*

Constraints

Subtask 1 (10%)

• 1 ≤ T ≤ 10
• 1 ≤ N, M ≤ 8
• 1 ≤ K ≤ min(8, N×M)

Subtask 2 (20%)

• 1 ≤ T ≤ 10
• 1 ≤ N, M ≤ 128
• 1 ≤ K ≤ min(128, N×M)

Subtask 3 (30%)

• 1 ≤ T ≤ 10
• 1 ≤ N, M ≤ 1024
• 1 ≤ K ≤ min(1024, N×M)

Subtask 4 (40%)

• 1 ≤ T ≤ 10
• 1 ≤ N, M ≤ 6144
• 1 ≤ K ≤ min(100000, N×M)