Amogh is a young wizard exploring the Land of Binary. In this land, numbers are magical creatures whose power is stored in their bits.
One day, Amogh encounters a creature with power n. To safely pass, he needs to drain all its power. He has a spell that can target the creature’s power one bit at a time, reducing its strength with each cast.
Amogh wants to know the minimum number of times he must cast his spell to completely drain the creature’s power.
Constraints
1≤t≤100 — number of test cases.
1≤n≤10^9 — power of each creature.
Input Format
First line: integer t — the number of creatures.
Next t lines: each line contains an integer n — the power of a creature.
Output Format
For each creature, print a single integer — the minimum number of spell casts needed to reduce its power to zero.
Example 1
Input:
3
5
7
8
Output:
2
3
1
Explanation:
Test case 1:
n = 5 → binary: 101 → 2 set bits → Amogh needs 2 spells.
Test case 2:
n = 7 → binary: 111 → 3 set bits → Amogh needs 3 spells.
Test case 3:
n = 8 → binary: 1000 → 1 set bit → Amogh needs 1 spell.
Log In to solve the Question