시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB153544143.158%

문제

집합 S는 다음과 같이 정의된다.

  1. 1은 S의 원소이다.
  2. X가 S의 원소라면 2X+1과 3X+1 또한 S의 원소이다.
  3. 위의 원소를 제외한 나머지는 S의 원소가 아니다.

위와 같은 집합 S가 있을 때 S의 N번째로 작은 S의 원소를 구하여라.

입력

첫 줄에 테스트 케이스의 수 T(1 ≤ T ≤ 200)가 입력된다. 그 후 각 테스트 케이스에 대해서 한 줄에 N(1 ≤ N ≤ 10,000,000)이 주어진다.

출력

각 테스트 케이스에 대해 N번째로 작은 S의 원소를 출력하라.

예제 입력 1

2
100
254

예제 출력 1

418
1461