#2155 J의 시험대비 비밀노트

11  1 s   128 MB  

Description

남중, 남고를 졸업한 J는 아주대학교 정보컴퓨터공학부 01학번으로 입학하였다. 남중, 남고를 졸업해 남들보다 더 각별하게 캠퍼스라이프에 대한 꿈과 희망을 가지고 있었다. 
 
그러나 현실은 자신이 생각한 캠퍼스라이프와는 전혀 달랐다. 매일 과제에 시달려서 생기는 피로와 밤새 프로그래밍하며 마신 에너지드링크 핫5의 빈 캔만 쌓여 나아갔다.
 
 
 
이렇게 1년이 지나 J는 열심히 공부한 노력의 결실로 정보컴퓨터공학부의 1학년 과 수석을 차지하였고, 드디어 자신이 꿈꾸던 귀엽고 눈웃음이 예쁜 여 후배가 신입생으로 입학하였다. 
 
첫눈에 반해버린 J는 그 여 후배에게 다가가려고 기회만 노리고 있었다. 
 
중간고사 기간이 오자 J는 1학년 전공과목인 컴퓨터프로그래밍 시험에 꼭 나올만한 핵심만 요약해둔 자신의 시험대비 비밀 노트(컴퓨터 파일)를 몰래 그 여 후배에게 전해주려 했다. 
 
그러나 그 여 후배와 함께 다니던 남 후배도 자신에게도 시험대비 비밀노트를 달라고 하는 것이었다. 
 
J는 그 여 후배에게만 시험대비 비밀노트를 주고 싶어했기 때문에 남 후배에게 시험대비 비밀노트를 주어야 할 것인지에 대해 고민을 하였다. 
 
시험대비 비밀노트는 이 둘을 통해서 후배들에게 전해질 것이 분명하였기 때문이다.
 
J는 그 여 후배에게만 시험대비 비밀노트를 주고 싶어했으나 그 남 후배에게도 간다면, 매년 들어오는 남 후배에게도 자신의 시험대비 비밀노트가 돌아다닐 것을 생각하니 자신의 의도와는 달라질 것을 생각하여 어떠한 트릭을 만들어 시험대비 비밀노트를 전해 주었다.
 
그 트릭은 아래의 규칙과 같다.
 
 
이렇게 트릭을 만든 J는 그 둘에게 전해주었고, J는 그 여 후배와 친해져 꿈꾸던 캠퍼스 라이프를 즐기게 되었다. 행복한 나날을 즐기던 J는 문득 자신의 트릭에 대해 궁금증이 생겼다.
 
매년 입학하는 신입생이 자신의 시험대비 비밀노트를 몇 개 가지고 있을 것인지에 대해서 궁금증을 가지게 되었다.
 
J는 이 문제에 대해 학번을 입력하면 그 학번의 신입생이 가지게 되는 시험대비 비밀노트의 개수를 구해주는 프로그램을 만들어 달라고 당신에게 부탁하였다.
 
J의 부탁을 들어 주자. 단, 시험대비 비밀노트를 받을 수 있는 신입생의 수는 무제한이라고 가정한다.

Input

첫 줄에는 테스트 케이스 T가 주어진다.

그리고 각 테스트케이스마다 N(1 <= N <= 40)이 주어진다. 이때 N는 찾기 원하는 학번이다.

Output

각 테스트케이스에서 주어진 입력 값에 대한 답을 20130511로 나눈 나머지를 출력하여라.

Sample Input

Sample Output

3
1
2
3
1
2
3

Source

2013 Ajou Programming Contest