#1740 Set Definition easy

27  2 s   128 MB  

Description

 

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

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

위와 같은 집합 S가 있을 때 S의 원소가 오름차순으로 정렬되어 있다고 할 때 N번 째 S의 원소를 찾는 프로그램을 작성한다.

 

Input

 

Test Case의 수 T가 입력된다. 그 후 각 Test Case에 대해서 한 줄에 N( 1 ≤ N ≤ 104)이 입력된다.

 

Output

 

각 Test Case에 대해 집합 S에서 N번째에 해당하는 원소를 출력한다.

Sample Input

Sample Output

2
100
254
418
1461

Source

PKU 2591