Một số nguyên ~M~ được cho là số tiêu chuẩn khi nó có dạng ~M=2^x +2^y (x,y≥0,x ≠y)~ Bạn được cung cấp một số nguyên ~N~, mỗi lần hành động bạn có thể thực hiện một trong hai loại thao tác:

• Tăng ~N~ lên 1
• Giảm ~N~ đi 1

Yêu cầu:

Hãy tính số lần hành động tối thiểu để ~N~ trở thành số tiêu chuẩn

Input:

• Dòng đầu tiên gồm số nguyên dương ~T (1≤T≤ 10^5 )~ - ứng với số test.
• ~T~ dòng tiếp theo, mỗi dòng gồm một số nguyên ~N (0≤N≤10^9)~

Output:

• In ra kết quả các test trên mỗi dòng

  Ví dụ:

Input

3
10
22
4

Output

0
2
1