Description
Olip the cat felt that cat life is too boring. So she wants to be a fish.
She asked RH the green sock for help.
But RH is busy with his data analysis homework, so if Olip wants his help, Olip help him write his homework.
His homework requires him to find the longest binary distance of an integer. The binary distance is the number of zeros "0" between two adjoining ones "1" in the binary representation of an integer.
For example, the binary representation of 37 is 100101, so 37 has two binary distances which are 2 and 1. And the longest binary distance is 2.
If there is no "0"s between two adjoining "1"s, the binary distance will be 0. e.g. 7 (111), has two binary distances = 0.
If the number of "1" in the binary representation is less than 2, the binary distance will be -1. e.g. 8 (1000) only has one binary distances = -1.
Input
First line is the number of testcases t 1 ≤ t ≤ 20)
Then, t lines follow
Each line contains one integer N (0 ≤ N ≤ 263 - 1).
Output
Output contains q lines and each line contain the longest binary distance of the input integer ended with '\n'.