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 N-th number in this list (members of the list are indexed from 1).

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¹⁸).

The output file should contain exactly T lines, with the i-th line containing exactly one integer, the answer for the i-th test case from the input file.

sample input	sample output
3 20 150 1	21 162 1