#10019Funny Encryption Method

A student from ITESM Campus Monterrey plays with a new encryption method for numbers. This method consists of the following steps:

This student failed Computational Organization, that's why this student asked the judges of ITESM Campus Monterrey's internal ACM programming contest to help find the number of 1-bits of these two representations so that he can continue playing.

You have to write a program that reads a number and gives as output the numbers $b_1$ and $b_2$.

Input

The first line will contain a number $N$ which is the number of cases that you have to process. Each of the following $N$ lines ($0 < N \le 1000$) will contain the number $M$ ($0 < M \le 9999$, in decimal representation) which is the number the student wants to encrypt.

Output

You will have to output $N$ lines, each containing the numbers $b_1$ and $b_2$ in that order, separated by one space, corresponding to that line's number to encrypt.

3
265
111
1234

3 5
6 3
5 5