Longest Binary Gap

Given a positive integer n, its binary representation can be written using the digits 0 and 1. A binary gap is any maximal sequence of consecutive zeros that is surrounded by ones at both ends. Your task is to find the length of the longest binary gap in the binary representation of the given number. If there is no binary gap, output 0.

For instance, the binary representation of 529 is 1000010001, which contains two gaps: one of length 4 and one of length 3. The correct answer is 4.

Note that sequences of zeros at the beginning or the end of the binary representation are not considered as gaps.

inputFormat

The input is read from standard input (stdin). The first line contains an integer T indicating the number of test cases. Each of the following T lines contains a single positive integer n.

outputFormat

For each test case, output the length of the longest binary gap in the binary representation of n on a separate line. The output is written to standard output (stdout).## sample

3
529
20
15

4
1
0