题目描述

考虑一个二进制串，它由 1 和 0 交替出现，并且以 1 开头。

长度为 n 时，这个串唯一确定，例如：

• n = 1 时为 1
• n = 2 时为 10
• n = 3 时为 101
• n = 6 时为 101010

把这个二进制串看作一个正整数的二进制表示。我们希望把它表示成若干个互不相同的二进制数之和，且这些二进制数必须都只由若干个连续的 1 组成，例如：

• 1
• 11
• 111
• 1111

也就是形如 2^k - 1 的数。

对于有些长度 n，这种表示存在；对于另一些长度则不存在。

例如：

• 1010₂ = 11₂ + 111₂
• 1010101₂ = 111₂ + 1111₂ + 111111₂
• 10101010101₂ 无法这样表示

请你编写程序，给定长度 n，求出一种合法表示中加数的个数；如果不存在这样的表示，输出 0。

输入格式

输入只有一行，一个正整数 n，表示交替二进制串的长度。

输出格式

输出一个非负整数：

• 若存在表示，输出其中加数个数；
• 若不存在，输出 0。

如果存在多种表示，输出任意一种对应的加数个数即可。

评分说明

测试点按两两成组计分。只有同组的两个测试都通过，才能获得这一组分数。

数据范围

• 1 <= n <= 2 × 10^9

子任务

• 10% 的测试组满足 n <= 60
• 30% 的测试组满足 n <= 10^3
• 60% 的测试组满足 n <= 10^6

样例

输入 1

6

输出 1

4

说明 1

长度为 6 的串是 101010₂，有一种表示为：

101010₂ = 1₂ + 11₂ + 111₂ + 11111₂

即：

42 = 1 + 3 + 7 + 31

输入 2

5

输出 2

0

说明 2

长度为 5 的串是 10101₂ = 21，无法表示成若干个互不相同的全 1 二进制数之和。