Champu has crush on a girl,so he wants to find out in which house she lives in. There are N houses in the colony of that girl and houses are numbered from 1 to N in clockwise order such that all houses form a circle. for N=12,the colony will look like 12 hours wall clock. Now champu finds an algorithm to mark(eliminate) the houses in the colony and when the colony is left with only unmarked house that house will be the house of his crush.the marking is done in turns starting from 1,for each turn champu starts by standing in front of some house saying 1,then moves to the next unmarked house saying 2 and so on until he reaches marking value of that turn.The marking value for kth turn is defined as k^3+k+1. At the end of each turn,house in front of him gets marked(i.e. house receiving marking value is marked) and the next turn is started from the next unmarked house clockwise from the house which just got marked. In the very first turn , Champu starts from the house number 1. when only one house is left unmarked,that house is the house of his crush.
Input:
Input contains only integer N which denotes the number of houses in the colony.
Output:
A single integer should be printed indicating house number of his crush.
Constraints:
1<=N<=10000
In the first turn, the marking value will be 3 (for k=1,from k^3+k+1). Champu starts from house number 1 saying one and goes to house number 2 saying two and finally to house number 3 saying three and mark it.in the 2nd turn ,marking value will be 11 ,so he starts from house number 4 saying one and moves to house number 1 saying two and then moves to house number 2 saying three and to house number 4 saying four and so on and mark the house number 1 for marking value 11. in 3rd turn ,he starts from house number 2 saying one and finally mark house number 2. now only house number 4 is left unmarked hence house number 4 is house of his crush.
