492. Hotel in Ves Lagos
Time limit per test: 0.25
second(s)
Memory limit: 262144
kilobytes
input: standard
output: standard
A new hotel is being built in the city of Ves Lagos. The hotel will have an infinite number of rooms (it is out of fashion to build hotels with finite numbers of rooms). The new hotel also tries to cater for superstitious guests.
The most common superstition in Ves Lagos is that the number 13 brings bad luck. Accordingly, only numbers whose decimal forms do not contain the substring "13" will be used to label the rooms in the new hotel. For example, the hotel will have rooms numbered 1, 3, 14, 31, 123, but will not have the rooms 13, 132, 913, 1308, 1313.
Let's consider the list of all room numbers, ordered increasingly. Find the
Nth number in this list (members of the list are indexed from 1).
Input
The input file contains several test cases. The first line of the file contains
T (1 ≤
T ≤ 100), the number of test cases. Each of the following
T lines describes one test case and contains the integer
N (1 ≤
N ≤ 10
^{18}).
Output
The output file should contain exactly
T lines, with the
ith line containing exactly one integer, the answer for the
ith test case from the input file.
Example(s)
sample input

sample output

3
20
150
1

21
162
1
