기념품

알고리즘 캠프 참가자 중 한 명에게 기념품을 준다. 참가자가 많아서 누구에게 줄지 고르기 어려우므로, 진행자는 게임으로 기념품을 받을 사람을 정한다.

게임을 시작하기 전에 참가자 $N$명이 원을 이루어 앉는다. 그리고 시계 방향으로 1번부터 $N$번까지 번호가 적힌 티셔츠를 입는다. 이 티셔츠는 게임 규칙에 쓰이지 않고, 사람을 쉽게 구분하려고 입는다.

게임은 여러 단계로 진행되고, 첫 단계는 1단계다. 각 단계가 시작될 때 진행자는 어떤 참가자 앞에 서 있다. 진행자는 그 사람 앞에서 "하나"를 외치고, 시계 방향으로 다음 사람에게 이동해 "둘"을 외친다. $t$단계에서는 $t^3$을 외칠 때까지 이 과정을 반복한다. 즉 1단계에서는 1까지, 2단계에서는 8까지, 3단계에서는 27까지 외친다.

한 단계가 끝나면 진행자 앞에 서 있는 사람, 곧 $t^3$을 외칠 때 앞에 있던 사람이 게임에서 빠진다. 그 사람이 빠진 뒤 진행자는 시계 방향으로 다음 사람에게 이동한다. 1단계에서 진행자는 1번 티셔츠를 입은 사람 앞에 서 있다. 게임은 원에 한 명만 남을 때까지 이어지고, 마지막까지 남은 사람이 기념품을 받는다.

참가자 수 $N$이 주어졌을 때 기념품을 받는 사람의 티셔츠 번호를 구하는 프로그램을 작성하시오.

첫째 줄에 캠프 참가자의 수 $N$이 주어진다. ($1 \le N \le 5000$)

첫째 줄에 기념품을 받는 사람이 입고 있는 티셔츠의 번호를 출력한다.