I I U P C   2 0 1 4

Problem G: Count It

 

 

Following is a code in C.

 

#include <stdio.h>

int num[1000006];

 

int main()

{

    int i,n,cas;

 

    num[0]=0;

    for(i=1;i<=1000000;i++) num[i]=num[i/2]+(i%2);

 

    scanf("%d",&cas);

 

    while(cas--)

    {

          scanf("%d",&n);

            printf("%d\n",num[n]);

    }

 

      return 0;

}

 

 

This code will work fine for values of n up to 106. But for higher value of n, the code will not work for memory, time constraints. You have to write a code which will give identical result for higher values of n.

 

Input

The first line contains number of test case T (1≤T≤500). Each of the next T lines contains an integer n (1≤n≤1018).

 

Output

For each of the test case you must output the answer in a line.

 

Sample Input

Output for Sample Input

3

4

5

6

1

2

2

 

Problem Setter: Sakib Shafayat