The Tom and Jerry Game | Competitive Programming Question | infoStud blogs

 As usual, Tom and Jerry are fighting. Tom has strength 

TS$TS$ and Jerry has strength JS$JS$. You are given TS$TS$ and your task is to find the number of possible values of JS$JS$ such that Jerry wins the following game.

The game consists of one or more turns. In each turn:

• If both TS$TS$ and JS$JS$ are even, their values get divided by 2$2$ and the game proceeds with the next turn.
• If both TS$TS$ and JS$JS$ are odd, a tie is declared and the game ends.
• If TS$TS$ is even and JS$JS$ is odd, Tom wins the game.
• If TS$TS$ is odd and JS$JS$ is even, Jerry wins the game.

Find the number of possible initial values of JS$JS$ such that 1≤JS≤TS$1\le JS\le TS$, there is no tie and Jerry wins the game.

Input

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

Output

For each test case, print a single line containing one integer ― the number of values of JS$JS$ such that Jerry wins the game.

Constraints

• 1≤T≤105$1\le T\le {10}^5$
• 1≤TS≤1018$1\le TS\le {10}^{18}$

Subtasks

Subtask #1 (20 points): T,TS≤100$T,TS\le 100$

Subtask #2 (80 points): original constraints

Example Input

2
1
11

Example Output

0
5

Explanation

Example case 1: We must have JS=TS=1$JS=TS=1$, but in this case, the game ends and a tie is declared in the first turn.

Example case 2: If JS∈{2,4,6,8,10}$JS\in \{2,4,6,8,10\}$, then JS$JS$ is even and TS$TS$ is odd, so Jerry wins the game in the first turn. Any odd value of JS$JS$ leads to a tie instead.

Code

/* package codechef; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Codechef

{

public static void main (String[] args) throws java.lang.Exception

{

// your code goes here

try {

Scanner sc =new Scanner(System.in);

int t = sc.nextInt();

for(int i=0;i<t;i++){

    long ts = sc.nextLong();

    while(ts%2==0){

        ts=ts/2;

    }

    System.out.println(ts/2l);

   

}

}

catch (Exception e) {

// TODO: handle exception

}

    

}

}