Given a positive integer n, find another integer p and non-negative integer o such that n = O2^P.

Example: For n = 24, o = 3 and p = 3.

Write a program that for each data set:

• Read a positive integer n,
• calculates the whole non-negative integer o and p such that n = O2^P,
• writes the result.

Input

The first line of input contains a positive integer d, indicating the number of data sets, 1 ≤ d ≤ 10

The following lines are data sets. Each data set consists of exactly one line that contains exactly one integer n, 1 ≤ n ≤ 10⁶.

Output

The output consists of exactly d lines, one line for each data set.

Line i, 1 ≤ i ≤ d, corresponding to the i-th entry and must contain two integers o and p separated by a single space so that n = O2^P

Example

Input:
2
24
32

Output:
3 3
1 5