#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 3 4 5 6
12893 – Count It 2/2 Sample Output 1 2 2