시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 9 1 1 16.667%

문제

In pursuit of one of the Infinity Gems, rumored to be in possession of Loki, Thor and the Avengers have reached what they believe to be one of Loki’s dens. However, their attempt to infiltrate is thwarted by a locked door. The Avengers need to quickly figure out which number (key) to enter on the keypad to gain access; however, they don’t the time to try the trillions of possible combinations. Thor notices a sequence of numbers on a nearby wall. Thor knows Loki well (they are half-brothers after all), and believes that the key is a Pythogorean triple, with the numbers drawn from the sequence.

A triple {x, y, z}, x < y < z is called a Pythogorean triple if: x 2 + y 2 = z 2 . So, for example, {3,4,5} is a Pythogorean triple, while {1,2,3} is not.

Your goal is to write a computer program that helps the Avengers. More specifically, given a sequence of positive integers x1, · · · , xn, all different from each other, your goal is find all the Pythogorean triples in that sequence.

For example, given a sequence, 13, 12, 3, 4, 5, there are two Pythogorean triples in it: {3, 4, 5} and {5, 12, 13}.

입력

The first line in the test data file contains the number of test cases (< 100). After that, each line contains one test case: the first number is n (3 ≤ n ≤ 50), the size of the sequence, and the following n numbers are the sequence (not necessarily in any order). None of the individual numbers are greater than 224.

출력

For each test case, you are to output the different Pythogorean triples. The exact form of the output is shown below.

예제 입력 1

4 
6 6 5 4 3 2 1 
3 3000000 5000000 4000000
5 13 12 3 4 5
6 1 2 4 8 16 32

예제 출력 1

Found Pythogorean triples:  {3 4 5}
Found Pythogorean triples:  {3000000 4000000 5000000}
Found Pythogorean triples:  {3 4 5} {5 12 13}
No Pythogorean triples found in the sequence.