Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Sắp đến kì thi tuyển sinh đại học, Bộ Giáo dục & Đào tạo quyết định đi kiểm tra chất lượng của các trường đại học trên cả nước. Có 3 tiêu chí bộ giáo dục đưa ra đó là: nghiên cứu (X), giảng dạy (Y), và cơ sở vật chất (Z). Tổng điểm được đánh giá bằng U = aX + bY + cZ, trong đó a, b, c là các hệ số mà Bộ Giáo dục đưa ra, và thỏa mãn a^2+b^2+c^2 = 1.

Tuy nhiên, các trường đại học lại bất đồng với Bộ Giáo dục về cách chọn các hệ số nhân a, b, c. Vì vậy họ đã yêu cầu thay đổi Bộ thay đổi hệ số nhân. Vấn đề này sinh khi có rất nhiều trường đòi thay đổi hệ số, thậm chí có trường đã còn đòi giảm hệ số thành hệ số âm. Bộ Giáo dục loay hoay không biết làm như thế nào? Các hệ số a, b, c vẫn là một ẩn số.

Một trường đại học được gọi là trường top 1, khi điểm đánh giá của trường đó lớn hơn hoặc bằng tất cả các trường còn lại. Các bạn hãy xác định xem các trường đại học nào có thể là trường top?

Input

Dòng đầu tiên là số bộ test T (T <= 10).

Mỗi bộ test gồm, dòng đầu tiên là số nguyên dương N (N <= 50) là số trường đại học. N dòng tiếp theo, mỗi dòng gồm 3 số nguyên X_i, Y_i, Z_i (<= 100) là điểm đánh giá của Bộ dành cho trường đại học thứ i với 3 tiêu chí đã cho.

Output

Với mỗi test, in ra trên một dòng N kí tự, kí tự thứ i là ‘T’ nếu trường thứ i có thể là trường top 1, và ghi ra ‘F’ trong trường hợp ngược lại.

Example

Input:
2
4
100 0 0
0 100 0
0 0 100
100 100 100
9
100 0 0
0 100 0
0 0 100
100 100 0
100 0 100
0 100 100
100 100 100
0 0 0
50 50 50

Output:
TTTT
TTTTTTTTF

Giải thích test 1:
Nếu Bộ GD chọn hệ số a = 1, b = 0, c = 0, khi đó trường 1 bằng điểm trường 4, 
và cả 2 trường này đều có thể là trường top 1.
Nếu Bộ GD chọn hệ số a = 0, b = 1, c = 1, khi đó trường 1 sẽ bằng điểm trường 4, 
và cả 2 trường này là trường top 1...

Giải thích test 2: 
Trường thứ 8, nếu Bộ GD chọn a = b = c = -1/sqrt(3), khi đó tổng điểm của 
trường 8 là U8 = 0, đạt điểm số cao nhất.
Trường thứ 9, cho dù Bộ GD chọn hệ số a, b, c như thế nào thì trường này 
cũng không thể có tổng điểm đạt cao nhất.