Người ta xây dựng một dãy vô hạn ~A~ chỉ gồm các chữ số ~0~, ~1~, ~2~ theo quy tắc sau:

Bước 0

Gán:

~a₁ = 0~

Bước k + 1

Giả sử sau bước ~k~ đã tạo được ~m~ chữ số đầu tiên của dãy:

~a₁a₂...aₘ~

Khi đó ở bước tiếp theo, nối thêm ~m~ chữ số:

~b₁b₂...bₘ~

với:

~bᵢ = (aᵢ + 1) mod 3~

Khi đó số lượng chữ số tăng gấp đôi sau mỗi bước.

Các giai đoạn đầu của dãy là:

~0 → 01 → 0112 → 01121220 → 0112122012202001 → ...~

Yêu cầu

Cho vị trí ~N~, hãy xác định chữ số thứ ~N~ của dãy ~A~.

Dữ liệu vào

Gồm nhiều dòng, mỗi dòng chứa một số nguyên dương ~N~.

Ràng buộc

• ~1 ≤ N ≤ 10^18~.

Kết quả

Với mỗi giá trị ~N~, in ra chữ số thứ ~N~ của dãy ~A~ trên một dòng.

Ví dụ

Dữ liệu vào

4
8

Kết quả

2
0

Giải thích

Dãy bắt đầu như sau:

~01121220...~

• Chữ số thứ ~4~ là ~2~.
• Chữ số thứ ~8~ là ~0~.