Consider the sequence of all integers that can be represented as 2^m + 2^n for integers 0 <= m < n, in increasing order. Given a positive integer k, your task is to find m and n for the kth element of the sequence.

Input

The first line is an integer T (T <= 10) is the number of test cases.

T lines follow each line contains one integer k is the math requirement. (k <= 10^9)

Output

For each test case in the two numbers m, n (m < n) is represented by the sequence number k.

Example

Input 1:
3
1
3
5

Output 1:
0 1
1 2
1 3

Input 2:
3
31
10
1997

Output 2:
2 8
3 4
43 63

Limited In 50% of tests, k <= 10^6

Explanation

The series starts with 3, 5, 6, 9, 10...

We need to find m and n for elements at indexes 1, 3 and 5, which have values 3, 6 and 10 respectively.

• 3 = 2^0 + 2^1
• 6 = 2^1 + 2^2
• 10 = 2^1 + 2^3