<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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 N-th 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 ≤ 1018).

Output
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.

Example(s)
sample input
sample output
3
20
150
1
21
162
1

<|response|>
1. Abridged Problem Statement
   We list all positive integers whose decimal representation does **not** contain the substring "13," in increasing order. Given a rank N (1 ≤ N ≤ 10^18), find the N-th number in this list. There are up to T (≤ 100) such queries.

2. Key Observations
   • N is up to 10^18, so we cannot generate the valid numbers one by one.
   • We need a way to **count** how many valid numbers are ≤ X, for any X.
   • If we can compute Count(X) = number of integers in [0..X] without "13," then the N-th valid number is the smallest X such that Count(X)−1 ≥ N (we subtract one to exclude zero).
   • Count(X) can be computed by a **digit dynamic programming** (digit‐DP) in O(L·2·2·10) where L ≈ 19 is the number of digits in X.
   • We then find the answer by **binary searching** X in a suitable range (e.g. [0..2N]) using the monotonicity of Count(X).

3. Full Solution Approach
   A. Digit‐DP to count valid numbers ≤ X
     1. Let S be the decimal string of X, of length L.
     2. Define a DP state dp[pos][lastIs1][is_smaller], representing the number of ways to fill digits from position pos to L−1 such that we never form "13":
        – pos: current digit index in [0..L]
        – lastIs1: 1 if the previous digit we placed was '1', else 0
        – is_smaller: 1 if the prefix we have built so far is already strictly less than the prefix of X (so the next digit d is free 0–9), else 0 (still tight)
     3. Transition at state (pos, lastIs1, is_smaller):
        – Determine the maximum digit we can place: up = is_smaller ? 9 : (S[pos]−'0')
        – For each d in [0..up]:
           • If lastIs1==1 and d==3, skip (that would form "13").
           • nextLastIs1 = (d==1) ? 1 : 0
           • nextSmaller = is_smaller | (d < up)
           • Add dp[pos+1][nextLastIs1][nextSmaller] to the current state's count.
     4. Base case: pos==L → return 1 (an empty suffix is one valid way).
     5. dp[0][0][0] gives Count(X) including zero. To ignore zero, subtract 1 when ranking.

   B. Binary Search for the N-th valid number
     1. We want the smallest X such that Count(X)−1 ≥ N.
     2. Set lo = 0, hi = 2·N (a safe upper bound since at worst half of numbers could be invalid).
     3. While lo ≤ hi:
        – mid = (lo + hi) // 2
        – If Count(mid)−1 ≥ N, record ans = mid, set hi = mid−1
        – Else set lo = mid+1
     4. After the loop, ans is the N-th valid number.

   Total complexity per query: O((log N) · L · states · 10) ≈ 60 · 19 · 2·2·10 ≈ 45 600 operations, which is fast enough for T ≤ 100.

4. C++ Implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int64_t n;

void read() { cin >> n; }

vector<vector<vector<int64_t>>> dp;

string bound_s;

int64_t rec(int pos, int last_1, int is_smaller) {
    if(pos == bound_s.size()) {
        return 1;
    }

    int64_t& memo = dp[pos][last_1][is_smaller];
    if(memo != -1) {
        return memo;
    }

    memo = 0;
    int up = bound_s[pos] - '0';
    int high = is_smaller ? 9 : up;
    for(int d = 0; d <= high; d++) {
        if(last_1 && (d == 3)) {
            continue;
        }

        memo += rec(pos + 1, d == 1, is_smaller | (d < up));
    }

    return memo;
}

int64_t cnt_below(int64_t bound) {
    bound_s = to_string(bound);
    dp.assign(bound_s.size(), {{-1, -1}, {-1, -1}});
    return rec(0, 0, 0);
}

void solve() {
    int64_t low = 0, high = 2 * n, mid, ans;
    while(low <= high) {
        mid = low + (high - low) / 2;
        // -1 as we shouldn't count 0.
        if(cnt_below(mid) - 1 >= n) {
            high = mid - 1;
            ans = mid;
        } else {
            low = mid + 1;
        }
    }

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation

```python
import sys
sys.setrecursionlimit(10000)

def count_upto(bound):
    """
    Return how many numbers in [0..bound] do not contain substring '13'.
    We use digit DP with memoization.
    """
    s = str(bound)
    L = len(s)
    # dp[pos][last1][is_smaller] = count of ways; use dict or list initialized to None
    dp = [[[None]*2 for _ in range(2)] for __ in range(L)]

    def rec(pos, last1, is_smaller):
        # If at end, there's exactly one valid number
        if pos == L:
            return 1
        if dp[pos][last1][is_smaller] is not None:
            return dp[pos][last1][is_smaller]
        limit = int(s[pos]) if not is_smaller else 9
        res = 0
        for d in range(0, limit+1):
            # Skip forming "13"
            if last1 and d == 3:
                continue
            nxt_last1 = 1 if d == 1 else 0
            nxt_smaller = is_smaller or (d < limit)
            res += rec(pos+1, nxt_last1, nxt_smaller)
        dp[pos][last1][is_smaller] = res
        return res

    return rec(0, 0, False)

def find_nth(n):
    # binary search X in [0..2n]
    lo, hi = 0, 2*n
    ans = hi
    while lo <= hi:
        mid = (lo+hi)//2
        # subtract 1 to ignore the count for zero
        if count_upto(mid) - 1 >= n:
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return ans

def main():
    data = sys.stdin.read().strip().split()
    T = int(data[0])
    idx = 1
    out = []
    for _ in range(T):
        n = int(data[idx]); idx += 1
        out.append(str(find_nth(n)))
    print("\n".join(out))

if __name__ == "__main__":
    main()
```
