미신을 따르는 스카이랩 타워

22세기에 이르러 구조 공학은 높이가 수천 킬로미터에 달해 우주까지 뻗는 궤도 타워(우주 엘리베이터)를 세울 수 있을 만큼 발전했다.

한 과학자 팀이 정지 궤도 너머까지 뻗는 연구 정거장으로 이런 타워를 하나 세우려고 한다. 이 타워의 층은 0부터 차례로 번호가 매겨진다. 그런데 많은 과학자가 미신을 강하게 믿어서, 번호 안 어딘가에 숫자 4가 들어 있거나 13이 부분 문자열로 들어 있는 층은 쓰지 않으려 한다. 예를 들어 4, 13, 14, 24, 40, 113, 130, 413 같은 번호는 모두 금지된다.

쓸 수 있는 층을 하나도 낭비하지 않기 위해, 설계팀은 층에 번호를 붙일 때 금지된 번호를 건너뛰기로 했다. 그래서 층 번호(라벨)는 다음과 같이 이어진다.

0, 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16, ...

(4를 건너뛰고, 13과 14를 건너뛰는 식이다.)

모든 층은 바로 아래 층보다 정확히 같은 높이 $h$만큼 높으며, 맨 아래(지상) 층의 높이는 0이다. 따라서 물리적 위치가 $p$인 층(지상을 0으로 두고 위로 세는 위치)의 높이는 $p \times h$이다. 번호를 건너뛰기 시작하면 층의 라벨과 물리적 위치가 달라진다는 점에 유의하라. 어떤 라벨의 물리적 위치는 그 라벨보다 앞서는 유효한 라벨의 개수와 같다.

층의 라벨과 층당 높이가 주어질 때, 그 층의 지상으로부터의 정확한 높이를 구하라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다.

이어지는 $T$개의 줄에는 각각 두 정수 $k$와 $h$가 주어진다.

• $k$ ($0 < k \le 10^{12}$) — 높이를 구하려는 층의 라벨.
• $h$ ($0 < h \le 1{,}000{,}000$) — 각 층의 높이.

주어지는 라벨 $k$는 항상 유효하다. 즉 숫자 4나 부분 문자열 13을 절대 포함하지 않는다.

각 테스트 케이스마다, 해당 층의 높이를 한 줄에 하나씩 출력한다.