Given positive integers $n$ and $k$, color $kn$ cells in an $n \times n$ grid black and the remaining cells white, such that the following conditions are satisfied:

• There are no three consecutive cells of the same color in any horizontal or vertical direction. Specifically:
  1. There exist no $1 \le i \le n, 1 \le j \le n - 2$ such that the cells at $(i, j), (i, j + 1), (i, j + 2)$ are all black or all white.
  2. There exist no $1 \le i \le n - 2, 1 \le j \le n$ such that the cells at $(i, j), (i + 1, j), (i + 2, j)$ are all black or all white.
• Each column contains exactly $k$ black cells.
• For any $i = 1, 2, \dots, k$, the difference in row coordinates between the $i$-th black cell from the top in any two adjacent columns is at most 1. Specifically, let the coordinates of the black cells in column $j$ be $(x_{1,j}, j), (x_{2,j}, j), \dots, (x_{k,j}, j)$, where $x_{1,j} < x_{2,j} < \dots < x_{k,j}$. Then for $1 \le i \le k$ and $1 \le j < n$, we have $|x_{i,j} - x_{i,j+1}| \le 1$.

Provide a valid coloring scheme, or determine that no such solution exists.

Input

The input is read from standard input. The first line contains a positive integer $T$ ($1 \le T \le 500$), representing the number of test cases. Each test case consists of one line containing two positive integers $n, k$ ($4 \le n \le 1000, 1 \le k \le n$), representing the size of the grid and the number of black cells in each column, respectively. It is guaranteed that the sum of $n^2$ over all test cases in a single test file does not exceed $10^6$.

Output

For each test case: If no valid coloring scheme exists, output a single line containing the string No. Otherwise, first output a single line containing the string Yes, followed by $n$ lines, each containing a string of length $n$ consisting only of the characters # and .. This represents the coloring of each row from top to bottom, where # represents a black cell and . represents a white cell. If there are multiple valid coloring schemes, any one is acceptable.

Examples

Input 1

3
4 2
6 1
9 5

Output 1

Yes
#..#
.##.
.##.
#..#
No
Yes
.#.#..##.
#.#.##..#
#.##..##.
.#..##.##
#..##.#.#
.##..#.#.
##.##.#.#
#.##.##..
.##.##.##

Note

For the first test case, here are several examples that do not satisfy the conditions:

In example 1, there are three consecutive white cells in the bottom-left corner. In example 2, the number of black cells in the first and fourth columns is incorrect. In example 3, there are three consecutive black cells in the top-left corner. In example 4, the difference in row coordinates of the second black cell in the third and fourth columns is greater than 1.

For the second test case, it is easy to see that no valid coloring scheme exists.

For the third test case, the validity of the answer is easily seen by labeling the black cells of different positions with different colors in the figure below: