A new batch of rum has arrived at the tavern “Admiral Benbow” — a total of 2ⁿ − 1 bottles, each numbered from 1 to 2ⁿ − 1. Additionally, there are 2ⁿ − 1 boxes, also numbered from 1 to 2ⁿ − 1.

Jimmy Hawkins wants to distribute all the rum bottles into the boxes, following an unusual rule: if he puts a bottle numbered k into the box with the same number k, an additional bottle appears, whose number equals the number of ones in the binary representation of k. However, if this number of ones equals k itself, then no new bottle appears.

Jimmy decided that he would only place the bottle numbered k into the box numbered k. He is also curious about how many bottles of rum will end up in each of the boxes numbered a_i. Help Jimmy find the answer!

The first line contains an integer n (1 ≤ n ≤ 60).

The second line contains an integer q — the number of boxes that interest Jimmy (1 ≤ q ≤ 10⁵).

The next line contains q integers a_i — the numbers of the boxes that are of interest to Jimmy (1 ≤ i ≤ q, 1 ≤ a_i ≤ 2ⁿ − 1).

Output a single line with q numbers — the number of rum bottles in the boxes with numbers a_i.

One bottle from the initial set will go into the box numbered 8. The box numbered 4 will also receive a bottle from the initial set and five additional ones obtained from boxes numbered: 30=11110₂, 29=11101₂, 27=11011₂, 23=10111₂, 15=1111₂.