Prime Pairs Sum

In this problem, you are given a list of integers. For each integer (n), you need to find all pairs of prime numbers ((p, q)) such that (p \leq q) and (p + q = n). The sequence of primes is obtained using the Sieve of Eratosthenes. If there exists no pair of primes that satisfy the condition, output "NO PAIRS" for that test case.

The mathematical condition you need to satisfy for each test case is: [ p + q = n, \quad \text{with } p \leq q \text{ and } p, q \text{ prime.} ]
An efficient solution involves precomputing the list of prime numbers up to the maximum value among the test cases using the Sieve of Eratosthenes, and then checking for each test case all possible pairs that add up to (n).

inputFormat

The input is read from standard input (stdin). The first line contains a single integer (T), representing the number of test cases. This is followed by (T) lines, each containing an integer (n) ((n \ge 1)).

outputFormat

For each test case, output one line on standard output (stdout): if there is at least one valid prime pair ((p, q)) with (p+q=n), print all pairs in increasing order (with respect to (p)) formatted as ((p, q)) and separated by a space. If no such pairs exist, print the string "NO PAIRS".## sample

3
10
12
27

(3, 7) (5, 5)
(5, 7)
NO PAIRS