Ban đầu dãy số có ~1~ số ~1~. Dãy biến đổi theo quy tắc: ~0~ thành ~1~ ~0~ và ~1~ thành ~0~ ~1~.

• Lần ~1~: ~0~ ~1~
• Lần ~2~: ~1~ ~0~ ~0~ ~1~
• Lần ~3~: ~0~ ~1~ ~1~ ~0~ ~1~ ~0~ ~0~ ~1~ ...
• Đếm số cặp số ~0~ liên tiếp sau lần biến đổi thứ ~n~.

Input

Dãy số nguyên, không biết trước số lượng nhưng số nào ~\le~ ~1000~.

Output

In ra kết quả với mỗi số đọc được.

Sample Input

1
2
3
4
5

Sample Output

0
1
1
3
5