Brujo Don Pedro#4893
Mexican brujo Don Pedro is very fond of making gold. For this, he usually uses two tools, which he calls the clonator and the summator. The clonator is a cheap device that allows you to make a duplicate of an existing gold ingot. The summator allows him to create a new ingot from two existing ingots, where the mass of the new ingot equals the sum of the masses of the initial ingots, and, miraculously, the original ingots do not disappear and preserve their mass! The summator is very expensive for brujos, and every use of it leads to a weakening of its magical power by bruchi (local units of magical energy, sometimes called mana in our homeland).
Once, Donald Knuth, while visiting the brujo, decided to mock him and asked him to produce a gold ingot with a mass of grams. Help the brujo lose the minimum amount of his magical power, given that initially he has a small piece of gold weighing gram.
The first line contains the number of tests (1 \leq n \leq 100). Then lines follow, each containing one positive integer (1 \leq m \leq 100) — the ingot mass (in grams), as requested by Knuth.
For each test, output on a separate line one number — the number of bruchi the poor brujo will lose in any case to fulfill the guest's order.
Example 1