Students of Walchand College of Engineering are insane about superheroes movies. One of which is "Batman vs Superman: Dawn of Justice".
But this time Batman needs to power up as to fight against Superman! Initially Batman has power equal to 0. But to fight against the mightiest Superhero Superman he requires power of magnitude N. So as to increase power to N he can perform two actions:
- Using 1$ he can increase his power by 1
- Using 2$ he can double his power
Despite of being super rich batman wants to power up to N using the least amount of money.
INPUT The first line of the input contains T(1<=T<=100) test cases and the next t lines contains N(1<=N<=10000)
OUTPUT Print on each line the output for each test case.
For case N=11, 0->1->2->4->5->10->11, which requires 8$ For case N=13, 0->1->2->3->6->12->13, which requires 8$
