우주 엘리베이터

중국이 우주 엘리베이터를 짓고 있다. 이 엘리베이터가 완성되면 탐사선과 위성을 훨씬 싼 비용으로 올려보낼 수 있어서, 과학 연구와 우주 관광에 모두 쓸 수 있다.

그런데 중국 사람들은 미신을 크게 신경 쓴다. 그래서 층 번호를 붙일 때 숫자 4가 들어가는 번호와 13이 연속으로 나오는 번호를 쓰지 않는다. 4층, 13층, 134층, 113층은 없지만 103층은 있다. 이 규칙에 따라 아래에서부터 층 번호는 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 15, 16, ... 순서로 붙는다.

층이 아주 많아서 번호를 하나씩 세어 붙이기는 어렵다. 아래에서 $N$번째 층에 붙는 번호를 구하는 프로그램을 작성하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 정수 $N$ 하나를 담고, 번호를 알고 싶은 층이 아래에서 몇 번째인지를 뜻한다. 입력의 끝까지 모든 테스트 케이스를 처리한다.

제약

• $1 \le N \le 10^{18}$

각 테스트 케이스마다 아래에서 $N$번째 층에 붙는 번호를 한 줄에 하나씩 출력한다.