There are many coloring problems and tile-filling problems in the world. This problem is one of them, dealing with L-trominoes, which are shapes formed by joining three square tiles of side length 1 in an L-shape. There are 4 shapes of L-trominoes, including rotations, as shown below.

Figure I.1: L-trominoes

Consider a square board consisting of $2^k \times 2^k$ tiles for a positive integer $k$. It is a well-known fact that no matter which single tile is removed from the board, the remaining part can be perfectly tiled without overlaps using L-trominoes. There can be multiple ways to place the L-trominoes in this manner.

After placing the L-trominoes, we want to color each L-tromino so that all L-trominoes are distinguishable. An L-tromino is said to be distinguishable if its color is different from all other L-trominoes that share a boundary (edge) with it.

Since these L-trominoes lie on a single plane, by the famous Four Color Theorem, they can be colored using at most 4 colors such that all L-trominoes are distinguishable. Interestingly, no matter which tile is removed, there always exists a placement of L-trominoes that can be colored distinguishably using at most 3 colors.

Given the size of the board and the position of the removed tile, find an example of placing and coloring the L-trominoes according to the above conditions.

Input

The first line contains an integer $T$, the number of test cases, and an integer $k$, which determines the size of the board. ($1 \le T \le 2^{10}$, $1 \le k \le 10$)

$T \times 2^{2k}$ is at most $2^{22}$.

Each of the following $T$ lines contains two space-separated integers $a$ and $b$ for each test case. ($1 \le a, b \le 2^k$)

Output

For each test case, output the coloring of the L-trominoes when the tile at the $a$-th row and $b$-th column of the $2^k \times 2^k$ board is removed, over $2^k$ lines. The $i$-th line represents the configuration of the $i$-th row of the board.

The color of each tile must be one of a, b, or c, and the removed tile must be represented by @. Of course, two L-trominoes sharing an edge cannot have the same color.

Examples

Input 1

2 1
1 2
2 2

Output 1

a@
aa
bb
b@

Input 2

1 3
7 6

Output 2

bbccaacc
baacabbc
ccabcbaa
cabbccab
aaccaabb
bbcbbacc
bcabc@bc
ccaaccbb

Note

Figure I.2: Incorrect answer because two adjacent L-trominoes share the same color across the boundary indicated by the red solid line.

Figure I.3: One of the possible correct answers for a $2^3 \times 2^3$ board when $a = 7, b = 6$.