Ciel and Receipt

Problem statement

A cafe uses a special training menu whose item prices are powers of two: 1, 2, 4 and so on up to 2048. Every price is available in unlimited quantity. The cashier receives a total p and wants to represent it with the fewest purchased items, making the printed receipt as short as possible while matching the amount exactly. Your task For each total p, find the minimum number of menu items with prices from {1,2,4,8,16,32,64,128,256,512,1024,2048} whose sum equals p. You may use the same price repeatedly. Return the count of items, not the number of different prices. Important details There is no item priced 4096 or higher, even though those are also powers of two. Larger totals may therefore need several 2048-priced items. Price 1 guarantees that every positive total is payable. Worked example For p = 2051, choose items priced 2048, 2 and 1. The total is exact and three items are sufficient.

Input format

First line: T. Next T lines: p.

Output format

Print the minimum item count for each total.

Constraints

1 <= T <= 1000; 1 <= p <= 100000.

Sample input

1
2051

Sample output

3