K. Class Optimization
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Lera Valeryevna's competitive class has $$$N$$$ children. The class is called competitive because among all the students in the parallel classes, her students write the best essays. It's all thanks to her unique approach to lessons. On Wednesdays, she talks about literature, and the students listen to her while sitting in pairs. And on Saturdays, the students have to read a book: during this lesson, Lera Valeryevna randomly divides the children into groups of three, and each group shares their reading experience.

Since sometimes students get sick, the attendance varies on different days. Recently, Lera Valeryevna noticed that Wednesday lessons are most effective when all the children are paired up: if someone sits alone at a desk, they get bored and lose focus on the lesson materials. Saturday lessons, on the other hand, are best when each group has exactly three people: if it's not possible to divide the children into groups of three and leave one or two children in a group, those children will get bored. And if the children gather in groups of four or more, they start interrupting each other, trying to talk about their own books, and the class becomes too noisy.

During a staff meeting, you, as the school director, overheard the following. When all $$$N$$$ children are healthy and come to school, some of Lera Valeryevna's lessons are not effective (though you didn't hear which ones exactly: Wednesdays, Saturdays, or both). You wanted to support the talented teacher and decided to announce additional spots in the competitive class. According to the regulations, you need to specify the exact number of spots, and you started to think. On one hand, you want to add as few new spots as possible to not burden Lera Valeryevna too much. On the other hand, after new children join the class, both Wednesdays and Saturdays should become effective lessons. Based on this, you decided to announce the minimum number of available spots, after which all lessons will become effective. What is this number?

Input

The input consists of a single line containing an integer $$$N$$$ ($$$3 \le N \le 29$$$) — the number of children in the class. It is guaranteed that it is impossible to divide $$$N$$$ children into pairs or groups of three (i.e., some of Lera Valeryevna's lessons are not effective).

Output

Print a single positive integer $$$M$$$ — the minimum number of children that need to be added to the class in order to divide the students into pairs and groups of three (i.e., to make all of Lera Valeryevna's lessons effective).

Examples
Input
5
Output
1
Input
26
Output
4
Note

In the first example, it is impossible to divide five children into pairs or groups of three. If one child is added, there will be six children, and they can be divided into pairs and groups of three. Note that the answer of 7 is incorrect: even though $$$5+7=12$$$ children can be divided into six pairs or four groups of three, seven is not the minimum number that satisfies this condition.

In the second example, there are 26 children, and they can be divided into pairs but not groups of three. To make it possible, four more children need to be added, resulting in a total of 30 children, which can be divided into fifteen pairs or ten groups of three.