Pairs with Prime Product

You are given a list of integers. Your task is to find all pairs of distinct elements (i, j) with i < j such that the product of the two numbers is a prime number. Note that a product P = a \times b can only be prime if one of the numbers is 1 and the other is a prime number.

For example, given the list [1, 2, 3, 5], the valid pairs are (1, 2), (1, 3) and (1, 5) since 1\times2=2, 1\times3=3, and 1\times5=5 are all prime numbers. If no such pair exists, output nothing.

The input is provided via standard input and the output should be printed to standard output.

Note: When there are no valid pairs, your program should output nothing.

inputFormat

The first line contains an integer n denoting the number of elements in the list.

The second line contains n space-separated integers.

outputFormat

For each valid pair, print a line containing the two integers separated by a single space. The order of pairs should follow the order of their appearance in the input (i.e. for indices i and j, with i < j).

If there are no valid pairs, print nothing.

## sample

4
1 2 3 5

1 2
1 3
1 5

</p>