THT Sơ Khảo C (2021) seq

#include <bits/stdc++.h>

using namespace std;
using ll = long long;


constexpr int N = 2e1 + 5;
constexpr ll Inf = 1e17;

ll p, k;
ll dp[N][2], g[N][2];
vector<int> s;

void Read()
{
    cin >> k >> p;
}

void Convert(vector<int> &s, ll v)
{
    s.clear();
    while (v)
    {
        s.emplace_back(v % 10);
        v /= 10;
    }
    reverse(s.begin(), s.end());
}

bool HaveNine(ll v)
{
    while (v)
    {
        if (v % 10 == 9)
            return true;
        v /= 10;
    }
    return false;
}

pair<vector<int>, ll> Greedy(ll l, ll r)
{
    vector<int> s, tmp;
    ll ans(0);
    for (; l <= r; ++l)
    {
        Convert(tmp, l);
        for (auto i : tmp)
        {
            while (!s.empty() && s.back() < i)
            {
                s.pop_back();
                ++ans;
            }
            s.emplace_back(i);
        }
    }
    return make_pair(s, ans);
}

ll Pow(ll a, ll b)
{
    ll ans(1);
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = ans * a;
        a = a * a;
    }
    return ans;
}

int getLog(ll v)
{
    int ans(0);
    for (; v >= 10; ++ans, v /= 10)
        ;
    return ans;
}

ll Get(ll v)
{
    ll ans(0);

    while (1)
    {
        if (v == 0)
            break;

        int lg = getLog(v);

        ll tmp = Pow(10, lg);
        ans += (lg + 1) * (v - tmp + 1);
        v = tmp - 1;
    }

    return ans;
}

ll f(int i, bool ok)
{
    if (dp[i][ok] != -1)
        return dp[i][ok];

    if (i == (int)s.size())
    {
        if (ok)
        {
            g[i][ok] = 1;
            return dp[i][ok] = 0;
        }
        else
        {
            g[i][ok] = 0;
            return dp[i][ok] = 0;
        }
    }

    dp[i][ok] = 0;
    g[i][ok] = 0;

    for (int j = 0; j < 10; ++j)
        if (ok || j <= s[i])
        {
            dp[i][ok] += f(i + 1, ok || (j < s[i]));
            if (j == 9)
                dp[i][ok] += g[i + 1][ok || (j < s[i])];
            g[i][ok] += g[i + 1][ok || (j < s[i])];
        }

    return dp[i][ok];
}

bool Check(ll v)
{
    memset(dp, -1, sizeof dp);
    memset(g, 0, sizeof g);

    ll cnt(0);
    ll x = v;
    while (x > 1 && !HaveNine(x))
        --x;

    Convert(s, x);
    cnt += Get(x - 1) - f(0, 0);

    cnt += Greedy(x, v).second;
    return cnt < k;
}

void Solve()
{
    ll l = 1, m, h = 1e14;
    while (l <= h)
    {
        m = (l + h) / 2;
        if (Check(m))
            l = m + 1;
        else
            h = m - 1;
    }

    ll x = l - HaveNine(l);
    while (x > 1 && !HaveNine(x))
        --x;

    memset(dp, -1, sizeof dp);
    Convert(s, x);

    if (p <= f(0, 0))
    {
        cout << "9\n";
        return;
    }

    ll r = k - (Get(x - 1) - f(0, 0));

    vector<int> t, tmp;

    for (ll i = x; i <= l; ++i)
    {
        Convert(tmp, i);
        for (auto i : tmp)
        {
            while (r > 0 && !t.empty() && t.back() < i)
            {
                --r;
                t.pop_back();
            }
            t.emplace_back(i);
        }
    }

    if (p <= f(0, 0) + (ll)t.size())
    {
        cout << t[p - f(0, 0) - 1] << "\n";
        return;
    }

    //cout << l << " " << f(0, 0) << "\n";

    ll digits = Get(l);

    p -= f(0, 0) + t.size();

    l = l + 1, h = 1e17;

    while (l <= h)
    {
        m = (l + h) / 2;
        if (Get(m) - digits < p)
            l = m + 1;
        else
            h = m - 1;
    }

    p -= Get(h) - digits;

    t.clear();
    for (ll v = l; v; v /= 10)
        t.emplace_back(v % 10);
    reverse(t.begin(), t.end());

    cout << t[p - 1] << "\n";
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}