# Ciel and Receipt Solution

Problem
Tomya is a girl. She loves Chef Ciel very much.

Tomya like a positive integer p, and now she wants to get a receipt of Ciel’s restaurant whose total price is exactly p.

Note that the i-th menu has the price 2i-1 (1 ≤ i ≤ 12). Find the minimum number of menus whose total price is exactly p.

#### Input

The first line contains an integer T, the number of test cases. Then T test cases follow. Each test case contains an integer p.

#### Output

For each test case, print the minimum number of menus whose total price is exactly p.

#### Sample Input

1
10

#### Sample Output

2

#### Explanations

In the first sample, examples of the menus whose total price is 10 are the following:1+1+1+1+1+1+1+1+1+1 = 10 (10 menus)1+1+1+1+1+1+1+1+2 = 10 (9 menus)2+2+2+2+2 = 10 (5 menus)2+4+4 = 10 (3 menus)2+8 = 10 (2 menus)Here the minimum number of menus is 2.

#### Solution

#include <iostream>
#include<math.h>
using namespace std;

int main() {
int T, ans, p;
cin>>T;
while(T>0) {
ans=0;
cin>>p;
for(int k=11; k>=0; k--) {
int c = pow(2,k);
//Subtracting multiples of 2 (2^i), starting from greatest to least
// to find the minimum number of menus
while(p-c>=0) {
p = p-c;
ans++;
}
}
T--;
cout<<ans<<endl;
}
return 0;
}