Prats is learning to count.But this is not a usual counting.He has been given the task to count number of trailing 0s in a binary representation of a number.
 

Input
First line of input contains T, number of test cases. Each of the next T lines contains a number N.
 

Output
Output the number of trailing 0s in binary representation of a number N.
 

Constraints

1 ≤ N ≤ 1000000
1 ≤ T ≤ 100

 

Example
Input:
2
4
7

Output:
2
0
 

Explanation
Example case 1. Binary form of 4 is 0100,hence number of trailing 0s is 2.
exec(input()*"print bin(input())[::-1].find('1');")