Sphere Online Judge



SPOJ Problem Set (tutorial)

9500. Bit counts

Problem code: BITCNTR

You are a detective working with Scotland Yard on a high-profile bank robbery case. The robber has left some trails in the form of numbers, which you believe will give you important clues about the robbery. Since you are genius, you know that the clues can obtained by converting the number in binary and counting the number of 1's. 

Input

The first line has a number t followed by t lines. Each line contains a number < 512.

Output

Output t lines corresponding to each number, such that each of the line contains the clue obtained from the number.

Example

Input:
5
2
3
1
0
11
Output:
1
2
1
0
3

Added by:Siddharth Kothari
Date:2011-09-07
Time limit:1s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All
Resource:Own

hide comments
2013-07-10 16:35:54 (Tjandra Satria Gunawan)(曾毅昆)
Seems that if BF code length is too long it'll increase memory usage and slow down the running time. Before I submit my code, I predict that my code will be 0.00s (Because I hardcoded all possible answer and just simply print the answer to stdout) and using 1.6M mem usage (because I only use max 5 BF cell on this problem). But in fact it's not like that.. My code run in 0.36s and using 2.5M memory usage.. Seems that the running time of (preprocess) on bff interpreter is also counted too.. and mem usage is not only BF cell used but also compiled BF code length, just like my own BF interpreter used on BFK_AUTO problem.
2013-01-26 23:48:13 Rodolfo Miquilarena
very simple bitmask problem :D
2012-11-19 23:18:49 Paul Draper
That is, a number satisfying 0<= number < 512
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.