C++爱好者 - 网友留言

Given a positive integer n, find the odd integer o and the non-negative integer p such that n=o2p. n=2的p次幂
Example
For n=24, o=3 and p=3.

Task
Write a program which for each data set:

reads a positive integer n,
computes the odd integer o and the non-negative integer p such that n=o2p,
writes the result.
Input

The first line of the input contains exactly one positive integer d equal to the number of data sets, 1 ≤ d ≤ 10. The data sets follow.
Each data set consists of exactly one line containing exactly one integer n, 1 ≤ n ≤ 106.

Output

The output should consists of exactly d lines, one line for each data set.
Line i, 1 ≤ i ≤ d, corresponds to the i-th input and should contain two integers o and p separated by a single space such that n=o2p.

Sample Input


1
24

Sample Output


3 3


 

--------------------next---------------------