1. Abridged Problem Statement
   Given a positive integer N (1 ≤ N ≤ 10^18), we list all positive integers whose decimal representation does *not* contain the substring "13", in increasing order. Find the N-th number in that list. There are up to T (≤100) test cases.

2. Detailed Editorial

   Idea: We need to handle N as large as 10^18, so we cannot generate numbers one by one. Instead, we
   a) Count, for any given bound X, how many integers in [0…X] do *not* contain "13".
   b) Binary‐search on X to find the smallest X for which that count (minus one for zero) is ≥ N.

   A. Counting with Digit DP
   - Represent X as a string of digits `D[0..L-1]`.
   - Define `dp[pos][last_is_1][is_smaller]` = number of ways to fill digits from `pos` to `L-1` such that we never form "13", given:
     • `last_is_1` = 1 if the previous digit was '1', else 0.
     • `is_smaller` = 1 if the prefix so far is already strictly less than X's prefix (so next digit is free 0–9), else 0 (still tight).
   - Transition: at position `pos`, choose digit `d` from 0 to `up = is_smaller ? 9 : D[pos]`. Skip if `last_is_1==1 && d==3` (that would form "13").
     new_last_is_1 = (d==1), new_is_smaller = is_smaller | (d < up).
   - Base case: pos==L → 1 valid way (the number built so far is OK).
   - Memoize by `dp[pos][last_is_1][is_smaller]`. Complexity: O(L · 2 · 2 · 10) ≈ 19·40 = 760 ops per call.

   B. Binary Search
   - We want the N-th valid positive integer. Let `count(X)` = number of valid ints in [0..X]. Note `count(0)=1` (the 0 itself). We exclude zero from ranking by subtracting 1.
   - Find the minimum `X` such that `count(X) - 1 ≥ N`. Standard binary search on X in [0..2N] (we know the N-th valid can't exceed 2N because at worst half of numbers are invalid, so an upper bound is 2N).

   Per test case:
   1) Read N.
   2) Binary search X. Each mid-value requires one digit-DP pass of ~O(760).
   3) Output the found X.

3. C++ Solution

```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;
}
```

4. Python Solution

```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()
```

5. Compressed Editorial
   - Use digit‐DP to count numbers ≤ X without substring "13".
   - DP state: (pos, last_was_1, is_smaller).
   - For query N, binary‐search the smallest X with count(X)−1 ≥ N.
   - Answer is that X.
