Dipu is a student of Mathematcis and solves the problems of Maths within seconds. So he boasts of his skill of solving problems based on Mathematics. One day , when Dipu was talking about his abilities before his friend Baidy , Baidy gives him a problem to solve. Dipu is in trouble this time and asks you for help.Problem given by Baidy is as following ---
let us define two functions f(n) and g(n) for a number n , such that
f(n) = number of even divisors of n.
g(n) = number of odd divisors of n.
find value of f(n) and g(n) for a given number n and print them.

Input

First line of input contains an integer t (no. of test cases to follow). Next t lines contains one integer n (the number) per line.

Output

Print exatcly t lines containing two integers each - f(n) and g(n) for the given n.

Constraints

1 <= t <= 1000
0 <= n <= 10^8

Example

Input:
3
4
7
36

Output:
2 1
0 2
6 3

Explanation

for 3rd test case , n = 36.
divisors of 36 are -- 1,2,3,4,6,9,12,18,36.
out of these divisors 6 are even and 3 are odd.
so answer is 6 3.