Factorization with Special Equation Constraint

Given a positive integer \(k\), there are \(k\) queries. In each query, you are given three positive integers \(n_i\), \(e_i\), and \(d_i\). Find two positive integers \(p_i\) and \(q_i\) such that:

\(n_i = p_i \times q_i\)

\(e_i \times d_i = (p_i - 1)(q_i - 1) + 1\)

You can assume that for each query there exists a unique solution satisfying the above conditions.

inputFormat

The first line contains a positive integer \(k\) indicating the number of queries.

Each of the following \(k\) lines contains three space-separated positive integers \(n_i\), \(e_i\), and \(d_i\).

outputFormat

For each query, output two space-separated positive integers \(p_i\) and \(q_i\) in a single line, which satisfy \(n_i = p_i \times q_i\) and \(e_i \times d_i = (p_i - 1)(q_i - 1) + 1\).

sample

3
15 3 3
35 5 5
77 61 1

3 5
5 7
7 11