You are given an integer K.

A function F is defined over non-negative integers as the following:

for i such that the given conditions hold true:

Determine the number of non-negative integers x such that

**|** = bitwise or**&** = bitwise and

**Example** for K = 6, possible x is 0, 1, 2, 3 and 4 as F(0) = 0

F(1) = 1

F(2) = 2

F(3) = 6

F(4) = 4

So, the answer is 5.

Constraints

*It was asked in nokia coding hackthon.*

I wasn't able to find any pattern to approach any optimal solution. How would you approach this problem?

not sure but $$$ x \triangle i = x - i$$$ seems like $$$ i \subseteq x$$$, so I guess now that you know the contribution of each bit, the growth of sum is very fast, that is it will reach to $$$ K $$$ in very less number of operations, so precalculate and then answer for each test case from your precalculated stuff.