Mexican Brujo Don Pedro is very fond of making gold. For this, he usually uses two tools, that he calls: a clonator and a summator. The clonator is a cheap device that allows you to make a duplicate of the existing gold ingot. The summator makes it possible to create a new one on the basis of two existing ingots, while the mass of the new ingot equals to the sum of masses of the initial ingots, and the miracle is that the initial ingots do not disappear anywhere 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 3 bruchi (local units of magical energy, sometimes called mana in our homeland).

Once Donald Knuth, a guest at the brujos, decided to mock him and made him make an ingot of gold with a mass of m grams. Help brucho to lose a minimum of his witchcraft, given that initially he has a small piece of gold weighing 1 grams.

Input

First line contains the number of tests n (1 ≤ n ≤ 100). Then n lines given, each contains one positive integer m (1 ≤ m ≤ 100) - the ingot weight (in grams), ordered by Knuth.

Output

For each test print on a separate line one number - the number of bruch force that the poor bruche will lose in any case, in order to fulfill the guest's order.