CF1775F.Laboratory on Pluto

As you know, Martian scientists are actively engaged in space research. One of the highest priorities is Pluto. In order to study this planet in more detail, it was decided to build a laboratory on Pluto.

It is known that the lab will be built of $n$ square blocks of equal size. For convenience, we will assume that Pluto's surface is a plane divided by vertical and horizontal lines into unit squares. Each square is either occupied by a lab block or not, and only $n$ squares are occupied.

Since each block is square, it has four walls. If a wall is adjacent to another block, it is considered inside, otherwise — outside.

Pluto is famous for its extremely cold temperatures, so the outside walls of the lab must be insulated. One unit of insulation per exterior wall would be required. Thus, the greater the total length of the outside walls of the lab (i. e., its perimeter), the more insulation will be needed.

Consider the lab layout in the figure below. It shows that the lab consists of $n = 33$ blocks, and all the blocks have a total of $24$ outside walls, i. e. $24$ units of insulation will be needed.

You should build the lab optimally, i. e., minimize the amount of insulation. On the other hand, there may be many optimal options, so scientists may be interested in the number of ways to build the lab using the minimum amount of insulation, modulo a prime number $m$.

Two ways are considered the same if they are the same when overlapping without turning. Thus, if a lab plan is rotated by $90^{\circ}$, such a new plan can be considered a separate way.

To help scientists explore Pluto, you need to write a program that solves these difficult problems.

众所周知，火星科学家正积极投身于太空研究。其中，冥王星是最高优先级的研究对象之一。为了更深入地研究这颗星球，决定在冥王星上建造一座实验室。

已知该实验室将由 $n$ 个大小相同的正方形模块构成。为方便起见，我们假设冥王星表面是一个被垂直与水平直线划分为单位正方形的平面。每个单位正方形要么被一个实验室模块占据，要么未被占据；且恰好有 $n$ 个单位正方形被占据。

由于每个模块均为正方形，故其具有四面墙。若某面墙与另一模块相邻，则该墙视为内墙；否则即为外墙。

冥王星以极低温度而闻名，因此实验室的所有外墙均需加装隔热层。每单位长度的外墙需消耗一单位隔热材料。因此，实验室外墙总长度（即其周长）越大，所需隔热材料就越多。

考虑下图所示的实验室布局。图中显示该实验室由 $n = 33$ 个模块组成，所有模块共有 $24$ 面外墙，即共需 $24$ 单位隔热材料。

你需要以最优方式建造该实验室，即最小化隔热材料用量。另一方面，可能存在多种达到最小隔热用量的建造方案，因此科学家可能还关心：在模某个质数 $m$ 意义下，有多少种不同的建造方式能达到最小隔热用量。

若两种方案在不旋转的情况下完全重合，则视为同一种方案。因此，若将某一实验室布局绕中心旋转 $90^{\circ}$，所得新布局可被视为一种独立的方案。

为协助科学家探索冥王星，你需要编写一个程序来解决这些难题。

The first line contains two integers $t$ and $u$ ($1 \le t \le 2\cdot 10^5$, $1 \le u \le 2$) — the number of test cases and the test type. If $u=1$, you need to find any way to build the lab in an optimal way, and if $u=2$, you need to calculate the number of ways to do it.

If $u=2$, then in the following line of input there is a prime integer $m$ ($10^8 \le m \le 10^9 + 9$), modulo which you need to calculate the number of ways.

Each of the following $t$ lines of input contains a description of a test case consisting of one integer $n$ ($1 \le n \le 4\cdot 10^5$) — the number of blocks the lab should consist of.

It is guaranteed that if $u=1$, then the sum of $n$ on all test cases does not exceed $8\cdot10^5$.

第一行包含两个整数 $t$ 和 $u$（$1 \le t \le 2\cdot 10^5$，$1 \le u \le 2$）—— 分别表示测试用例的数量和测试类型。若 $u=1$，你需要找出一种最优方式来建造实验室；若 $u=2$，你需要计算建造方案的总数。

若 $u=2$，则输入的下一行包含一个质数 $m$（$10^8 \le m \le 10^9 + 9$），你需要将方案总数对 $m$ 取模。

接下来的 $t$ 行每行描述一个测试用例，包含一个整数 $n$（$1 \le n \le 4\cdot 10^5$）—— 表示实验室应由多少个方块组成。

保证：若 $u=1$，则所有测试用例的 $n$ 值之和不超过 $8\cdot10^5$。

For each test case, output the answers in the format below, separating them with a newline. The output format depends on $u$ in the input data.

If $u=1$, in the first line you need to print two integers $h$ and $w$ —the height and width of the area in which the lab should be built. Then, in each of the following $h$ lines, you must output a line $s_i$ consisting of $w$ characters "#" and ".". If the $j$-th character of the row $s_i$ is "#", then the corresponding square must contain a block of laboratory, otherwise, it is considered empty. Thus, we get a matrix of symbols. The condition must also be met that the first and last rows of the matrix, as well as the first and last columns, must have at least one character "#", otherwise we could output the same lab layout, but with smaller $h$ and $w$. If there are many options to build an optimal lab, you can print any of them.

If $u=2$, you need to print two integers $p$ and $c$ — the number of outside walls in an optimal lab, and the remainder of the number of ways by prime modulo $m$.

对于每个测试用例，按以下格式输出答案，各答案之间用换行符分隔。输出格式取决于输入数据中的 $u$。

若 $u=1$，则在第一行输出两个整数 $h$ 和 $w$ —— 分别表示实验室应建造区域的高度和宽度。随后的 $h$ 行中，每行输出一个长度为 $w$ 的字符串 $s_i$，该字符串仅由字符 # 和 . 组成。若字符串 $s_i$ 的第 $j$ 个字符为 #，则对应方格必须放置实验室的一个方块；否则该方格视为空。由此得到一个符号矩阵。此外，还需满足：该矩阵的第一行与最后一行、第一列与最后一列均至少包含一个 # 字符；否则，可输出相同布局但更小的 $h$ 和 $w$。若存在多种构造最优实验室的方案，任选其一输出即可。

若 $u=2$，则输出两个整数 $p$ 和 $c$ —— 分别表示最优实验室中外墙的数量，以及方案总数对质数模 $m$ 取余后的余数。

Consider the second example.

If $n=1$, the only way to build a lab is to place a single block. In this case, the perimeter will be equal to four.

When $n=2$, you must place two blocks side by side. This can be done either vertically or horizontally, so there are two ways. It is easy to see that the lab has six outside walls in this case.

For $n=7$, all the $22$ optimal plans are shown in the picture below.

考虑第二个例子。

当 $n=1$ 时，建造实验室的唯一方法是放置一个方块。此时，周长等于 4。

当 $n=2$ 时，必须将两个方块并排放置。这既可水平放置，也可垂直放置，因此共有两种方式。容易看出，此时实验室具有 6 面外侧墙壁。

当 $n=7$ 时，全部 22 种最优方案如下图所示。