컴퓨터 변환

컴퓨터에 처음에는 한 자리 숫자 $1$ 하나로 이루어진 수열이 저장되어 있다. 매 시간 단계마다 컴퓨터는 모든 숫자 $0$을 수열 $1,0$으로, 모든 숫자 $1$을 수열 $0,1$로 동시에 바꾼다.

따라서 첫 번째 단계 후에는 수열 $0,1$이 되고, 두 번째 단계 후에는 $1,0,0,1$, 세 번째 단계 후에는 $0,1,1,0,1,0,0,1$이 되며, 이런 식으로 계속된다.

$n$단계 후의 수열에는 연속한 두 개의 $0$(즉 $0,0$) 쌍이 몇 개 나타나는가?

입력의 각 줄에는 자연수 $n$ ($0 < n \le 1000$)이 하나씩 주어진다. 입력의 끝까지 각 줄을 처리한다.

각 $n$에 대해, $n$단계 후의 수열에 나타나는 연속한 $0$ 쌍의 개수를 한 줄에 하나씩 출력한다.