HLP_RAMS - Topper Rama Rao

no tags 

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, { nC0, nC1 ... nCn }.

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

Input

First line contains t (1 <= t <= 105), the number of test cases. Next t lines contain one integer per line, denoting n (0 <= n <= 1012).

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.


hide comments
sanyam19: 2018-01-06 09:38:51

gr8 Q... bitset implementation gave AC....
AC in 2 go.. forgot to change datatype during paasing an integer n in declaring a fuction.... :)
feeling confident.

iharsh234: 2016-09-18 13:21:51

don't forget long long int :)

vineetpratik: 2016-07-06 12:49:58

better don't use built in bit counter , gave me 1 wa

kesucool: 2016-06-05 18:05:44

Great Question. Bitset implementation gave WA whereas bit operators ACC. :)

ov3rk1ll: 2016-06-03 09:59:46

use __builtin_popcountl() when doing this with bits got 3 wa :( with just __builtin_popcount()

vikikkdi: 2016-05-17 08:45:56

my 100th :-)(think bitwise logic)

sonupmandal: 2016-03-27 05:09:02

same logic JAVA -> TLE
C++ -> AC

Shashank Tiwari: 2015-10-31 23:25:30

Lucas Theorem

Manish Das Mohapatra: 2015-09-22 07:58:58

BIT WISE operators saved the day.

Rajat Singh: 2015-09-17 10:07:59

using cin gives wrong answer!!!!!


Added by:nitish rao
Date:2014-03-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:My own Problem