Farmer John züchtet Kühe. Moderne Verfahren nutzen längst verstorbene preisgekrönte Bullen, sodass keine Bullen nötig sind. Die Futtermenge steuert die Kälberzahl; jede Kuh erhält gleich viel und produziert gleich viele Kälber. Aus einer Kuh sollen nach einigen Generationen $N$ Kühe werden.

Bei $N = 12$ füttert er die erste Kuh für drei Kälber. Wenn diese Generation alt genug ist, füttert er jede für vier, also zuletzt zwölf. Nach Nachwuchs wird die Mutter verkauft; nur die jüngste Generation bleibt.

Jede Generation produziert jede Kuh mindestens zwei Kälber, ohne Obergrenze, dank einer sehr kräftigen Rasse.

Für die ganze Zahl $N$ ($1 \le N \le 2{,}000{,}000{,}000$): Auf wie viele Arten erhält er aus einer Kuh $N$? Die Zahl der Arten für $N$ überschreitet $2{,}000{,}000{,}000$ nicht.

Eingabe

• Zeile 1: ganze Zahl $N$.

Ausgabe

• Zeile 1: Anzahl der Arten, $N$ Kühe zu erhalten.

Beispiele

Eingabe 1

12

Ausgabe 1

8

Hinweis

Erläuterung der Ausgabe

Eine Art für zwölf ist $(2,2,3)$: zwei Kälber je Kuh in Generation eins, zwei in Generation zwei, drei in Generation drei, insgesamt zwölf junge Kälber. Die sieben anderen sind $(2,3,2)$, $(3,2,2)$, $(3,4)$, $(4,3)$, $(12)$, $(2,6)$, $(6,2)$.

Autor: Mihai Stroe, 2002