Given a natural number
N - the number of numbers (1<=N<=10
3), and non-prime natural numbers
ai< /sub> (1<=a
i<=10
5). For each number ai print its smallest and largest divisors not equal to 1, 2, 3 and ai< /sub>/2, ai/3, ai.
Input
In the first line, the program receives a natural number N (1<=N<=103) as input. The following N lines give numbers ai (100<=ai<=10 5), each number on a separate line.
Imprint
For each number ai print two space-separated numbers on a separate line - its smallest and largest divisors other than 1, 2, 3 and ai/2, ai/3, a i.
Examples
| # |
Input |
Output |
| 1 |
5
731
1034
460
618
667 |
17 43
11 94
4 115
6 103
23 29 |