Rama Rao is the topper of his branch. One of his friends was jealous of it. So, he poses a question to test Rama Rao and is as follows:

For a given n, find the number of even and odd numbers among the set, { ⁿC₀, ⁿC₁ ... ⁿC_n }.

Rama Rao was having hard time solving it. He hopes you can help him.

Input

First line contains t (1 ≤ t ≤ 10⁵), the number of test cases. Next t lines contain one integer per line, denoting n (0 ≤ n ≤ 10¹²).

Output

For each test case, output two space separated integers specifying the number of even numbers and odd numbers respectively.

Example

Input:
2
3
4
Output:
0 4
3 2

Explanation:

for 3, values are: 1 3 3 1. All are odd. Hence 0 4.

for 4, values are: 1 4 6 4 1. Hence 3 2.