D. Logo
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Svetozar's favorite number is the number $$$n$$$. His favorite color is red. His favorite geometric shape is a square. And his least favorite activity is logo design.

That is why he assigned this to you. The requirements for the logo are simple:

  • The logo is a square consisting of squares. In other words, for some $$$m$$$ the logo is a grid of $$$m \times m$$$ squares.

  • Among the $$$m^2$$$ small squares of the logo, exactly $$$n$$$ must be red, and the rest must be uncolored.

  • The red squares must cover at least one subsquare of size $$$(m - 1) \times (m - 1)$$$.

  • The uncolored squares must form a single region connected by sides. In other words, from any uncolored square it is possible to reach any other uncolored square by repeatedly moving to an uncolored square adjacent by one of the $$$4$$$ sides (left, right, bottom, or top). Leaving the logo itself is forbidden. If there are no uncolored squares, this condition is satisfied automatically.

  • $$$m$$$ must be as small as possible, because then the individual squares will be as large as possible.

Generate any logo that satisfies the conditions above.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$): the number of test cases. Then, $$$t$$$ test cases follow.

The only line of a test case contains an integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$): the number of red squares in the logo.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print the logo in the following format.

In the first line, print an integer $$$m$$$ ($$$1 \leq m \leq 10^6$$$).

In the next $$$m$$$ lines, print the logo: each line must contain exactly $$$m$$$ characters '#' (a red square) or '.' (an uncolored square).

If there are several valid logos, print any.

Example
Input
3
1
2
10
Output
1
#
2
##
..
4
####
###.
###.
....