Windy is doctor. He has a lot many bottles of medicine in his house; one bottle is poisonous, while the others are not. The bottles have labels on them, so windy knows which one is poisonous.
One day, some mice came to his house, bit off the labels and made the bottles mixed up. Windy was angry because he had to recognize the poisonous one.
As a punishment to the mice, he decided to catch them and feed them with the medicine. Poisonous medicine would kill the mice one hour later while the nonpoisonous ones would have no effect. He would feed all the mice he caught, wait for one hour to see the effect, and then he should be able to tell the poisonous one from the nonpoisonous ones.
Catching live mice was difficult. Windy wanted to know, with his n bottles of medicine, how many mice he should catch at least, in order to tell the poisonous one from the nonpoisonous ones?
The first line contains one integer t, specifying the number test cases.
Then t lines follow, each containing one integer n, which is the number of bottles Windy has.