Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Discuss Home ProblemSet Status Ranklist 19 Contest LoginRegister Exam
2017 ACM 集训队预选排名~      报名入口
趣味编程比赛报名入口
Problem 1077. -- Bigger Square Please...

Bigger Square Please...

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 0  Solved: 0
[Submit][Status][Discuss]

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][Discuss]

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