Every competitive programmer’s dream is to participate in the ICPC World Finals, and so is Eren’s. In order to fulfill his preparation he was going through the previous ICPC problem set and found three problems among which the $1^{st}$ one requires “Binary Search”, $2^{nd}$ one requires “DP” (Dynamic Programming) and the third one requires “Graph Theory”. These are among some of the topics that every competitive programmer masters. However, he has time to solve only one problem, because he has to participate in a Mathforces round later, which is a website that hosts weekly contests on Math. To pick which one to solve he decided to call his friend Armin and pick a non-negative integer $N$, based on which he will determine which problem he will attempt.

He decided to divide the number that Armin picked by$3$. If the remainder of the division is$0$then he will solve the problem that requires “DP”, if it is$1$then he will solve the one that requires “Binary Search” and if it is$2$then he will solve the “Graph Theory” one.

Now you have the number $N$ that Armin picked. Can you tell which problem Eren solved before he participated in the Mathforces round?

Input

The only line of input contains a positive integer $N$ the number Armin picked.