불길한 층

Rar the Cat은 IOI 2014를 위해 대만에 갔을 때 호텔에 묵었다. 그동안 그는 호텔 건물에서 특정 층이 '없다'는 사실을 깨달았다. 즉, 4와 13을 부분 문자열로 포함하는 수는 층 번호에서 빠져 있었다. 4와 13은 불길한 수로 여겨져 번호 매기기에서 의도적으로 제외되기 때문이다. 편의상 불길한 수를 제외하는 이 번호 체계를 행운 번호 체계라고 부르자. 아래 표는 행운 번호 체계와 일반 번호 체계에서 처음 20개 층을 보여준다.

그러나 Rar the Cat은 이런 번호 체계가 타당하지 않다고 느끼며 행운 번호 체계와 일반 번호 체계 사이에서 층을 변환할 수 있기를 원한다. 예를 들어 행운 번호 체계에서 6층은 일반 번호 체계에서 5층이고, 15층은 실제로 12층이다. 따라서 Rar the Cat은 행운 번호 체계의 층 번호가 주어지면 그것이 일반 번호 체계에서 몇 층인지, 그 반대의 경우도 계산하기를 원한다.

입력은 한 줄에 정수 N 하나로 시작한다. N은 Rar the Cat이 변환해 주기를 원하는 층 번호의 개수이다.

이어서 N줄이 각각 정수 2개씩 주어지며, i번째 줄에는 Ti와 Xi가 들어 있다.

Ti가 1이면 Xi를 행운 번호 체계에서 일반 번호 체계로 변환하여 결과를 한 줄에 출력한다. 그러나 Xi가 행운 번호 체계에서 유효한 수가 아니면 대신 −1을 출력한다.

Ti가 2이면 Xi를 일반 번호 체계에서 행운 번호 체계로 변환하여 결과를 한 줄에 출력한다.

총 N줄에 정수 1개씩 출력한다. 각 i에 대해 Ti와 Xi의 답을 출력한다. 답은 64비트 부호 있는 정수에 들어감이 보장된다.

• 0 < N ≤ 100 000
• Ti = 1 또는 2
• 0 < Xi ≤ 10^16