Souvenir

One participant of an algorithm camp receives a souvenir. There are too many participants to pick one by hand, so the host runs a game to decide who gets it.

Before the game starts, the $N$ participants sit in a circle. They then put on shirts numbered 1 through $N$ in clockwise order. The shirts play no part in the rules; they only make the participants easy to tell apart.

The game runs in stages, and the first stage is stage 1. At the start of every stage the host is standing in front of some participant. The host shouts "one" in front of that participant, then moves to the next participant clockwise and shouts "two". In stage $t$ the host repeats this until shouting $t^3$. So the host counts up to 1 in stage 1, up to 8 in stage 2, and up to 27 in stage 3.

When a stage ends, the participant standing in front of the host, that is the participant the host faced while shouting $t^3$, leaves the game. After that participant leaves, the host moves to the next participant clockwise. In stage 1 the host stands in front of the participant wearing shirt 1. The game continues until one participant remains in the circle, and that last participant receives the souvenir.

Given the number of participants $N$, write a program that finds the shirt number of the participant who receives the souvenir.

The first line contains the number of camp participants $N$. ($1 \le N \le 5000$)

Print the shirt number of the participant who receives the souvenir on the first line.