Highest Power of Two Divisor

Given a positive integer N, determine the highest power of 2 that divides N. In other words, find the largest integer of the form \(2^k\) such that \(2^k\) divides N and \(2^{k+1}\) does not divide N.

For example, if N is 12, then the answer is 4 because 12 can be written as \(4 \times 3\), and 4 is the highest power of 2 dividing 12.

inputFormat

The input is given via stdin. The first line contains an integer T representing the number of test cases. Each of the following T lines contains a single positive integer N.

outputFormat

For each test case, output a single line with the highest power of 2 that divides N, printed to stdout.

3
8
12
18

8
4
2