# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* still_me

*the_hyp0cr1t3, rivalq*

**Testers:***iceknight1093*

**Editorialist:**# DIFFICULTY:

TBD

# PREREQUISITES:

None

# PROBLEM:

Given N, find three distinct positive integers A, B, C such that the pairwise product of any two is a divisor of N, and the product of all three is a multiple of N.

# EXPLANATION:

For convenience, let’s suppose 1 \leq A \lt B \lt C.

First, note that since AB, BC, AC should all be divisors of N, each of A, B, C must themselves be divisors of N.

We’d like all three to be distinct, so if N = 1 or N is prime, the answer is `-1`

since N doesn’t even have three distinct divisors.

Also note that C = N is impossible.

## Why?

We’ll always have B \gt 1, so if C = N then BC would be strictly larger than N, and hence cannot be a divisor of it.

This further tells us that if N = p^2 for a *prime* p, then the answer is `-1`

(since p^2 doesn’t have three distinct factors smaller than it).

In every other case, finding an answer is always possible.

One simple construction is as follows: pick A = 1, B = p, C = N/p where p is some prime dividing N. It’s easy to verify that this always works when N is neither a prime nor a square of a prime.

So, we need to do the following:

- Check whether N is prime.
- Check whether N is the square of a prime.
- If N is neither, find some prime divisor of N.

This is easy to do in \mathcal{O}(\sqrt N) by slightly modifying the standard primality check algorithm: simply iterate over numbers from 2 to \sqrt{N}, and the first time you find a divisor, return it.

Ensure that the divisor you return isn’t the square root of N; and if you don’t find any such divisor, the answer is `-1`

.

# TIME COMPLEXITY:

\mathcal{O}(\sqrt{N}) per testcase.

# CODE:

## Code (Python)

```
def findprime(n):
for i in range(2, n+1):
if i*i > n: break
if n%i == 0: return i
return -1
for _ in range(int(input())):
n = int(input())
p = findprime(n)
if n == 1 or p == -1 or p*p == n: print(-1)
else: print(1, p, n//p)
```