Số tiêu chuẩn

Điểm: 100

Thời gian: 1.0s

Bộ nhớ: 560M

Input: STNUM.inp

Output: STNUM.out

Tác giả:

h1a4c3k

Dạng bài

Ta gọi số nguyên $M$ là số tiêu chuẩn nếu có có dạng $M=2^x+2^y$ , với $x,y$ là hai số nguyên không âm phân biệt.
Bạn có một số nguyên dương $N$ . Trong một bước bạn có thể tăng hoặc giảm $N$ đi $1$ .

Yêu cầu: Tính số bước ít nhất để biến $N$ thành số tiêu chuẩn.

Input, Output và Scoring

Input (STNUM.inp)

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

Output (STNUM.out)

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

Sample

Input (STNUM.inp)

Output (STNUM.out)

0
2
1

Notes

Số $10=2^1+2^3$ là một số tiêu chuẩn nên không cần dùng thao tác nào.
Số $22$ cần $2$ thao tác để đưa về số $20=2^2+2^4$ .
Số $4$ cần $1$ thao tác để đưa về số $5=2^0+2^2$ .

Bình luận

Không có bình luận nào.