## Welcome To SDIBT ACM-ICPC Online Judge

Problem 1077. -- Bigger Square Please... ## Bigger Square Please...

Time Limit: 1 Sec Memory Limit: 64 MB

Submit: 0 Solved: 0

[Submit][Status][Forum]## Description

Tomy has many paper squares. The side length (size) of them ranges from 1 to N - 1, and he has an unlimited number of squares of each kind. But he really wants to have a bigger one - a square of size N.
He can make such a square by building it up from the squares he already has. For example, a square of size 7 can be built from nine smaller squares as shown below:
There should be no empty space in the square, no extra paper outside the square, and the small squares should not overlap. Further, Tomy wants to make his square using the minimal number of possible squares. Can you help?

## Input

The first line of the input contains a single integer T indicating the number of test cases. Each test case consists of a single integer N, where 2<=N<=50.

## Output

For each test case, print a line containing a single integer K indicating the minimal number of squares needed to build the target square. On the following K lines, print three integers x, y, l indicating the coordinates of top-left corner ( 1<=x, y<=N) and the side length of the corresponding square

## Sample Input

3
4
3
7

## Sample Output

4
1 1 2
1 3 2
3 1 2
3 3 2
6
1 1 2
1 3 1
2 3 1
3 1 1
3 2 1
3 3 1
9
1 1 2
1 3 2
3 1 1
4 1 1
3 2 2
5 1 3
4 4 4
1 5 3
3 4 1

## HINT

## Source

[Submit][Status][Forum]

HOME
Back

한국어 中文 English

All Copyright Reserved 2008-2010 SDIBT TEAM

GPL2.0 2003-2010 HUSTOJ Project TEAM

Anything about the Problems, Please Contact Admin:admin