E. Beautiful Board
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

María has a board with $$$n \times m$$$ square cells distributed in $$$n$$$ rows and $$$m$$$ columns.

María wants to paint the cells in black and white such that the following two properties are satisfied:

  • The number of white cells must be equal to the number of black cells.
  • The number of pairs of adjacent cells of the same color must be equal to the number of pairs of adjacent cells of different colors. (Two cells are considered adjacent if they share a side).

Can you help María paint her board?

Input

The first line contains an integer $$$T$$$, the number of test cases.

Each case consists of a line with two integers $$$n$$$ and $$$m$$$.

Output

For each test case, the output should contain a first line with the word "SI" if it is possible to paint the board in a way that satisfies the conditions, and with the word "NO" if it is not possible. If the answer is "SI", the output should include $$$n$$$ more lines with $$$m$$$ characters each describing a possible way to paint the board that satisfies the properties, indicating with "." the cells painted white and with "#" the cells painted black. If there are multiple possible solutions, any of them can be provided.

Scoring

$$$1 \leq T \leq 50$$$.

$$$1 \leq n, m \leq 1000$$$, the sum of $$$n \cdot m$$$ for all cases is less than $$$2 \cdot 10^6$$$.

20 points: $$$n, m \leq 6$$$, $$$T \leq 20$$$.

20 points: $$$n, m \leq 20$$$, the sum of $$$n \cdot m$$$ for all cases is less than $$$2000$$$.

15 points: $$$n = 2$$$, the sum of $$$n \cdot m$$$ for all cases is less than $$$2 \cdot 10^4$$$.

15 points: $$$n = m$$$.

30 points: No additional restrictions.

Example
Input
3
2 4
3 3
4 6
Output
SI
##..
.##.
NO
SI
###..#
#..#.#
..#...
####..