## IPSC 2018

## Problem P – Partitioning a square

In this problem you are given a number *n* and your task is to produce a square of letters.

The square must have the following properties:

- Each letter is one of the first
*n* lowercase English letters (`a`

-`z`

).
- Each of those
*n* letters occurs the same number of times.
- All occurrences of each letter form one 4-connected region (explained below).
- The square is
**as small as possible**.

We say that the occurrences of some letter *X* form a 4-connected region if it is possible to travel from any *X* to any other *X* by only moving one step up/down/left/right at a time without stepping onto a letter other than *X*.

Below is an example of a 6 × 6 square divided into *n* = 4 equally large 4-connected regions. (Note that this is not the *smallest possible* square that can be divided into 4 regions.)

```
aaaaab
aaaabb
bbbbbd
bddddd
cdddcc
cccccc
```

The first line of the input file contains an integer *t* specifying the number of test cases. Each test case is preceded by a blank line.

Each test case consists of a single line with a single positive integer *n*.

In the **easy subproblem P1** we have *t* = 1 and the only test case has *n* = 4.

In the **hard subproblem P2** we have *t* ≤ 50 and each *n* is between 1 and 26, inclusive.

### Output specification

For each test case, output several lines. The first of those lines should contain an integer *s*: the side length of your square. The rest of the output for that test case should consist of *s* lines, each containing *s* lowercase letters.

### What to submit

**Do not submit any programs.** Your task is to produce and submit the correct **output files** `p1.out`

and `p2.out`

for the provided input files `p1.in`

and `p2.in`

.

### Example

**Input:**

```
1
2
```

**Output:**

```
2
ab
ab
```