Pythagorean Triples

Interview

Time limit1sMemory limit128 MB

Summary
Given up to 50 distinct positive integers, list all Pythagorean triples x<y<z present in the set, sorted lexicographically, or report that none exist.
Level

Medium4 of 10

Topics
Hash map, Math, Sorting, Brute force
Solved
No attempts yet

Problem

The Avengers have reached one of Loki's dens, but a locked keypad blocks the way. Thor is convinced the key is a Pythagorean triple made from three numbers on a sequence written on a nearby wall. Help them find every such triple.

A set of three distinct integers {x,y,z}\{x, y, z\} with x<y<zx < y < z is called a Pythagorean triple when x2+y2=z2x^2 + y^2 = z^2. For example, {3,4,5}\{3, 4, 5\} is a Pythagorean triple, while {1,2,3}\{1, 2, 3\} is not.

Given a sequence of distinct positive integers x1,x2,…,xnx_1, x_2, \dots, x_n, find every Pythagorean triple whose three members all appear in the sequence.

Input

The first line contains the number of test cases TT (T<100T < 100).

Each of the next TT lines describes one test case. The line begins with an integer nn (3≤n≤503 \le n \le 50), the length of the sequence, followed by the nn distinct positive integers of the sequence in arbitrary order. No number exceeds 2242^{24}.

Output

Print the answer for each test case on its own line, in the same order as the input.

If the sequence contains at least one Pythagorean triple, print the keyword, then two spaces, then every triple. Write each triple as {x y z} with x<y<zx < y < z and a single space between the numbers, and separate consecutive triples with a single space. List the triples in increasing order, first by xx, then by yy, then by zz. The line reads exactly:

Found Pythogorean triples:  {x y z} {x y z} ...

If the sequence contains no Pythagorean triple, print exactly:

No Pythogorean triples found in the sequence.

The output keyword is spelled Pythogorean, exactly as shown.

Examples1

  1. Example 1

    Input
    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
    
    Expected output
    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.