집합의 정의

집합 $S$는 다음 규칙으로 정의된다.

1. $1$은 $S$의 원소이다.
2. $X$가 $S$의 원소이면 $2X+1$과 $3X+1$도 $S$의 원소이다.
3. 이 두 규칙으로 만들어지지 않는 수는 $S$의 원소가 아니다.

$S$는 집합이므로 한 값이 여러 방법으로 만들어져도 원소는 하나로 센다.

$S$의 원소를 작은 것부터 나열했을 때 $N$번째 값을 구하라.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 200$)가 주어진다. 이어지는 $T$개의 줄에 각각 정수 $N$ ($1 \le N \le 10^7$)이 하나씩 주어진다.

각 테스트 케이스마다 $S$의 $N$번째로 작은 원소를 한 줄에 하나씩 출력한다.