Binary Number

Time limit

Memory limit

128 MB

Problem

A binary number consists only of 0 and 1. From one binary number, create the next one by replacing every character at the same time: 0 becomes 10, and 1 becomes 01. The first binary number is 1. The first few numbers are:

1 -> 01 -> 1001 -> 01101001 -> ...

Given an integer N, determine how many groups of consecutive 0s appear in the N-th binary number. For N = 4, the binary number is 01101001, which contains three groups of consecutive 0s.

Input

The first line contains an integer N (1 <= N <= 1,000).

Output

Print the answer on the first line.