Po rất thích toán học. Trước khi bắt đầu thi học kỳ, Po lấy bài tập toán của cô giáo đã giao ôn tập. Nhiệm vụ của Po là phải chuyển số nguyên dương ~n~ thành số nguyên dương ~m~ có dạng ~2^x+2^y~ trong đó ~x~ và ~y~ là hai số nguyên không âm và ~x≠y~ sao cho số thao tác chuyển là ít nhất. Mỗi thao tác chuyển Po thực hiện như sau:

• Cộng ~1~ vào ~n~, hoặc
• Trừ ~1~ từ ~n~.

Rất nhanh chóng Po đã giải quyết xong bài tập nhưng không biết kết quả có chính xác không? Hãy gải bài toán này và so sánh kết quả với Po.

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên ~t~ ~(1≤t≤100000)~ cho biết số test.
• ~t~ dòng tiếp theo, mỗi dòng ghi một số nguyên ~n~ ~(1≤n≤10^9)~ cho biết một bài toán Po cần giải.

**Kết quả: **

• Với mỗi test theo thứ tự trong input in ra một số nguyên cho biết số thao tác ít nhất cần chuyển từ ~n~ thành ~m~. Mỗi kết quả ghi trên một dòng.

Ví dụ:

Input

3
10
22
4 

Output

0
2
1