Với một dãy nhị phân bất kỳ, ta biến đổi dãy nhị phân như sau:

• ~1 → 01~
• ~0 → 10~
• Như vậy, với dãy bắt đầu là ~1~, sau bước biến đổi thứ nhất, ta sẽ thu được dãy ~01~.
• Sau phép biến đổi thứ ~2~, ta thu được ~1001~.
• Sau phép biến đổi thứ ~3~, ta thu được ~01101001~.
• …

Người ta muốn tính xem, sau ~n~ bước biến đổi, sẽ thu được dãy gồm có bao nhiêu cặp ~2~ số ~0~ đứng liên tiếp.

Input

• Gồm một số test, mỗi test được ghi trên một dòng, mỗi dòng ghi một số nguyên không âm ~n~

Output

• Với mỗi test, ghi ra số cặp 2 số 0 đứng liên tiếp.

Sample Input

2
3

Sample Output

1
1

Subtask

• Có ~40%~ số test ứng với ~40%~ số điểm của bài có ~n≤ 20~;
• Có ~40%~ số test ứng với ~40%~ số điểm của bài có ~n≤ 50~;
• Có ~20%~ số test khác ứng với ~20%~ số điểm còn lại của bài có ~n≤1000~.