#1119 Set Definition

27  2 s   256 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 ≤ 107)이 입력된다.

 

Output

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

 

Sample Input

Sample Output

2
100
254
418
1461

Source

PKU 2591