Maximum Consecutive Ones in Binary

In this problem, you are given a list of non-negative integers. For each integer, you need to determine the maximum number of consecutive 1's in its binary representation. More formally, for a given integer (N) with binary representation (b_1b_2\dots b_k) (without any leading zeros), your task is to compute the quantity (\max{\text{length}(s)}), where (s) ranges over all contiguous sequences of 1's in the binary representation. Note that if the number is 0, then the answer is 0. For example, the binary representation of 7 is 111, so the answer is 3.

inputFormat

The first input line contains an integer (n) ((1 \leq n \leq 10^5)), the number of non-negative integers. The second line contains (n) space-separated integers, each in the range ([0, 10^9]).

outputFormat

Output (n) integers separated by a space. Each integer represents the maximum number of consecutive 1's in the binary representation of the corresponding input number.## sample

3
5 7 0

1 3 0