PROG0323 - Politeness

A strictly positive integer is polite if it can be written as the sum of two or more consecutive strictly positive integers. 7 is an example of a polite number as it can be written as 3+4. Polite numbers are sometimes also called staircase numbers because the Young diagrams, graphically representing the partitions of a polite number into consecutive integers, resemble staircases.

young diagram
A Young diagram visually representing the polite expansion 15 = 4 + 5 + 6.

Some numbers can be written as a sum of consecutive numbers in multiple ways. 15, for example, can be written in three different ways: 

1 + 2 + 3 + 4 + 5
4 + 5 + 6
7 + 8

The amount of ways in which a number can be written as a sum of two or more strictly positive integers, is called the politeness of a number. Numbers that are a power of two can't be written as a sum of two or more consecutive numbers. Those numbers have a politeness of 0, therefore they are impolite.

Input

A number $n \in \mathbb{N}_0$.

Output

A number that represents the politeness of the number $n$.

Example

Input:

15

Output:

3

Een strikt positief natuurlijk getal is beleefd als het kan geschreven worden als de som van twee of meer opeenvolgende strikt positieve natuurlijke getallen. Het getal 7 is bijvoorbeeld beleefd omdat het kan geschreven worden als 3 + 4. Beleefde getallen worden soms ook trapgetallen genoemd, omwille van de trapvorm van de Young diagrammen die een grafische voorstelling weergeven van de ontbinding van een beleefd getal in opeenvolgende natuurlijke getallen.

young diagram
Een Young diagram dat de beleefde voorstelling van het getal 15 = 4 + 5 + 6 grafisch weergeeft.

Sommige getallen kunnen op verschillende manieren geschreven worden als de som van twee of meer opeenvolgende getallen. Zo kan 15 bijvoorbeeld op de volgende manieren geschreven worden:

1 + 2 + 3 + 4 + 5
4 + 5 + 6
7 + 8

Het aantal manieren waarop een getal kan geschreven worden als de som van twee of meer opeenvolgende strikt positieve natuurlijke getallen wordt de beleefdheid van het getal genoemd. Elk getal dat een macht van twee is kan niet geschreven worden als de som van twee of meer opeenvolgende getallen. Dergelijke getallen hebben een beleefdheid van 0, en zijn dus onbeleefd.

Invoer

Een getal $n \in \mathbb{N}_0$.

Uitvoer

Een getal dat de beleefdheid van het getal $n$ aangeeft.

Voorbeeld

Invoer:

15

Uitvoer:

3

Added by:Peter Dawyndt
Date:2013-02-05
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:PY_NBC
Resource:None

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.