Internet Problem Solving Contest

• Easy input data set – P1
• Hard input data set – P2

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

Input specification

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