Number of 1 Bits

For each number, count the 1 bits in its binary representation (its Hamming weight or popcount). For example 11 = 1011₂ has three.

Input:

• line 1: q
• next q lines: one non-negative integer x each

Output: for every x, its number of 1 bits on its own line.

Constraints: 1 ≤ q ≤ 10⁵, 0 ≤ x < 2³².

Watch out: x can be ≥ 2³¹, so it does not fit in a signed 32-bit int — use long / long long / unsigned. Trick: x & (x − 1) removes the lowest set bit, so the loop runs only once per 1 bit.