집합 S는 다음과 같이 정의된다.</p>

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의 원소를 출력하라.

예제 입력

2
100
254

예제 출력

418
1461