Mô tả và yêu cầu

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 𝑛 thành số nguyên dương 𝑚 có dạng
2𝑥 + 2𝑦 trong đó 𝑥 và 𝑦 là hai số nguyên không âm và 𝑥 ≠ 𝑦 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 𝑛, hoặc
+ Trừ 1 từ 𝑛.
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 𝑡 (1 ≤ 𝑡 ≤ 100000) cho biết số test.
+ 𝑡 dòng tiếp theo, mỗi dòng ghi một số nguyên 𝑛 (1 ≤ 𝑛 ≤ 109) cho biết một bài toán Po
cần giải.

Dữ liệu ra

+ 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ừ 𝑛 thành 𝑚. Mỗi kết quả ghi trên 1 dòng.

Ví dụ

Input       Output
                                             3           0
                                             10          2
                                             22          1
                                             4