B. Vlad and Shapes

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Vladislav has a binary square grid of n×n�×� cells. A triangle or a square is drawn on the grid with symbols 11. As he is too busy being cool, he asks you to tell him which shape is drawn on the grid.

• A triangle is a shape consisting of k� (k>1�>1) consecutive rows, where the i�-th row has 2⋅i−12⋅�−1 consecutive characters 11, and the central 1s are located in one column. An upside down triangle is also considered a valid triangle (but not rotated by 90 degrees).

Two left pictures contain examples of triangles: k=4�=4, k=3�=3. The two right pictures don't contain triangles.

• A square is a shape consisting of k� (k>1�>1) consecutive rows, where the i�-th row has k� consecutive characters 11, which are positioned at an equal distance from the left edge of the grid.

Examples of two squares: k=2�=2, k=4�=4.

For the given grid, determine the type of shape that is drawn on it.

Input

The first line contains a single integer t� (1≤t≤1001≤�≤100) — the number of test cases.

The first line of each test case contains a single integer n� (2≤n≤102≤�≤10) — the size of the grid.

The next n� lines each contain n� characters 00 or 11.

The grid contains exactly one triangle or exactly one square that contains all the 11s in the grid. It is guaranteed that the size of the triangle or square is greater than 11 (i.e., the shape cannot consist of exactly one 1).

Output

For each test case, output "SQUARE" if all the 11s in the grid form a square, and "TRIANGLE" otherwise (without quotes).

Example

input

Copy

6

3

000

011

011

4

0000

0000

0100

1110

2

11

11

5

00111

00010

00000

00000

00000

10

0000000000

0000000000

0000000000

0000000000

0000000000

1111111110

0111111100

0011111000

0001110000

0000100000

3

111

111

111

output

Copy

SQUARE
TRIANGLE
SQUARE
TRIANGLE
TRIANGLE
SQUARE

解题说明：此题是一道几何题，需要判断图形到底是三角形还是正方形，可以看相邻两行都是1的个数，相同的话就是矩形，否则就是三角形.

#include<stdio.h>
#include<string.h>

int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int n, cnt, prev = 0, sq = 0, tr = 0;
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
		{
			char a[n + 1];
			scanf("%s", a);
			cnt = 0;
			for (int j = 0; j < n; j++) 
			{
				if (a[j] == '1')
				{
					cnt++;
				}
			}
			if (prev != 0) 
			{
				if (cnt == prev)
				{
					sq = 1;
				}
				else
				{
					tr = 1;
				}
			}
			if (cnt > 0)
			{
				prev = cnt;
			}
		}
		if (sq)
		{
			printf("SQUARE\n");
		}
		else
		{
			printf("TRIANGLE\n");
		}
	}
	return 0;
}