All Tracks>Problem
[Debugging] Naruto Vs Sasuke
★★★★★

1

1 votes
Problem

Problem Statement

Naruto and Sasuke are two comrades in one of the three men squad of leaf village hidden in the leaves. Although they are part of the same team still they fight a lot amongst them for some of the obvious reasons.
One such reason was that Naruto was always jealous about Sasuke because he always gets the girls and he was way cooler than the other academy students naruto even calls him Mr. perfect. On the other hand, Sasuke was jealous because the guy he always calls a loser has caught up to him and is performing exceptionally well.

One day they decided to settle this by fighting vigorously till their death to decide who is more powerful and worthy. Kakashi being the leader of their 3-men squad already knows the outcome of this fight and he has devised a trick to explain the winner of this fight.
He defines the trick in terms of chakra level(power level).

Suppose Naruto has chakra level N and Sasuke has chakra level S at the begining of the fight and the fight happens in rounds then, during a particular round :

  • If Naruto's chakra level (N) is even and Sasuke's chakra level(S) is odd, Naruto wins the fight. 
  • If Sasuke's chakra level(S) is even and Naruto's chakra level(N)  is odd, Sasuke wins the fight.
  • If both Naruto's chakra level(N) and Sasuke's chakra level(S) are even, their values get divided by 2, and the fight proceeds with the next round.
  • If both Naruto's chakra level(N) and Sasuke's chakra level(S) are odd, a tie is declared and the fight ends.


Use Kakashi's trick to find number of possible initial values of Naruto's Chakra level(S) such that Naruto wins the fight against Sasuke.


Input:

  • The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
  • The first and only line of each test case contains a single integer S.

Output:

  • For each test case, print a single line containing one integer ― the number of values of N such that Naruto wins the fight.


Constraints:

  • 1<=T<=103
  • 1<= S <= 1018
  • 1<= N <= S
Sample Input
3
8
16
15
Sample Output
0
0
7
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

Example case 1 :  In this case , a tie is declared therefore there are 0 possible initial values of N such that Naruto wins the fight .

Example case 2 : same as example case 1 .

Example case 3 : Initial values of N can be {2,4,6,8,10,12,14} such that Naruto wins the fight since the S is odd in the first round. 

Editor Image

?