Four of your friends live in four different villages. You plan to visit one of these friends every afternoon. At the three intersections leading to the villages, there is an arrow sign pointing to the direction you need to follow. Initially, all arrows point to the left road. When passing an intersection, you have the habit to switch the arrow so that it points to the opposite direction.

On the first day you take the road on the left at the first intersection and the left road at the second intersection, reaching the house in village A. On the second day you turn right at the first intersection, then left at the second intersection, so that you arrive at the house in village C.

Input

An integer $$d \in \mathbb{N}_0$$ that indicates the number of the day on which you want to visit a friend.

Output

The letter corresponding to the village where the friend lives that you visit on day $$d$$.

Example

Input:

30

Output:

C