Given an integer N and M(initially M=0). You can do the following operations - Create an integer K and add 2^k to M. Create an integer K and subtract 2^k from M. Find the minimum number of operations to make M equal to N

Input Format- The first line of input contains a single integer T-number of test case The first line of each test case contains a single integer M.

Constraint- N<=2*10^5 |M|<=10^9

Expected Complexity per test case -log(|M|);