Given a number you are required to find the $Largest$ $prime$ $divisor$ and the number of $Distinct$ $prime$ $factors$ it has.

Input :

The first line of the input consists of a single integer t (the number of test cases) ( $1\le t \le 1000000$ )

The next t lines consists of a single integer p representing the query ( $2 \le p \le 10000000$ )

Output :

Output contains two space separated integers representing the $Largest$ $prime$ $divisor$ and number of $Distinct$ $prime$ $factors$ .