Hrpa

Το αγαπημένο χόμπι του Mirko και του Slavko είναι να ανταγωνίζονται μεταξύ τους σε μαθηματικά παιχνίδια. Αυτή τη φορά πήραν ένα σωρό από ~N~ βότσαλα και συμφώνησαν με τους ακόλουθους κανόνες:

1. Ο Mirko είναι ο πρώτος που παίζει, μετά ο Slavko, μετά πάλι ο Mirko, μετά ο Slavko και ούτω καθεξής.
2. Ο Mirko μπορεί να πάρει οποιονδήποτε αριθμό βότσαλων (μεταξύ ~1~ και ~N~, συμπεριλαμβανομένων αυτών) από το σωρό κατά την πρώτη του κίνηση.
3. Σε καθέναν από τους παρακάτω γύρους, ο τρέχων παίκτης πρέπει να πάρει τουλάχιστον 1 βότσαλο και επιτρέπεται να πάρει το πολύ διπλάσιο από τα βότσαλα που πήρε κατά την προηγούμενη γύρο ο άλλος παίκτης. Φυσικά, δεν μπορεί κανείς να πάρει περισσότερα βότσαλα από την υπόλοιπη ποσότητα στο σωρό.
4. Ο παίκτης που παίρνει το τελευταίο βότσαλο είναι ο νικητής.

Τόσο ο Mirko όσο και ο Slavko παίζουν βέλτιστα (αν είναι δυνατό για έναν παίκτη να κερδίσει τον άλλο, αυτός ο παίκτης θα κερδίζει πάντα). Πρέπει να βρούμε τον ελάχιστο αριθμό βότσαλων που πρέπει να πάρει ο Mirko κατά την πρώτη του στροφή, έτσι ώστε να είναι σίγουρο ότι θα κερδίσει το παιχνίδι.

Είσοδος

Η πρώτη και μοναδική γραμμή εισόδου περιέχει τον θετικό ακέραιο αριθμό ~N\;(2 \leq N \leq 10^{15})~, τον αριθμό των βότσαλων στον αρχικό σωρό.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον απαιτούμενο ελάχιστο αριθμό βότσαλων που πρέπει να αφαιρέσει ο Mirko κατά την πρώτη του στροφή.

Παραδείγματα

input

4

output

1

Επεξήγηση του 1ου παραδείγματος:

Ο Mirko έχει 4 επιλογές από τις οποίες μπορεί να διαλέξει: μπορεί να πάρει 1, 2, 3 ή 4 βότσαλα από το σωρό. Αν πάρει και τα 4 βότσαλα φυσικά θα κερδίσει, αλλά αυτή δεν είναι η ελάχιστη λύση. Πρέπει να ελέγξουμε τις υπόλοιπες εναλλακτικές. Εάν ο Mirko πάρει μόνο ένα βότσαλο, ο Slavko μένει με έναν σωρό των 3, αλλά μπορεί να πάρει το πολύ 2. Ο Slavko δεν μπορεί να πάρει όλα τα βότσαλα, αλλά ο Mirko θα μπορεί να πάρει όλα τα εναπομείναντα βότσαλα στον επόμενο γύρο του, κερδίζοντας το παιχνίδι. Συμπεραίνουμε ότι το 1 είναι η ελάχιστη λύση για αυτήν την περίπτωση δοκιμής.

input

7

output

2

input

8

output

8