Given a non-negative integers N. You have to find the largest odd divisor of N.

Input

Input starts with an integer T (1<=T<=5000) denoting the number of test cases. Each test case contains an integer N (1<=N<=10¹²).

Output

For each test case print the case number and the largest odd divisor of N.

Problem Setter: Md Abdul Alim, CEO and Founder at CodeMask