Digit Queries

#include <bits/stdc++.h>
using namespace std;

int64_t k;

pair<bool, int64_t> f(int64_t x) {
  int d = to_string(x).size();
  int64_t qtd = 0, aux = 9;
  for (int i = 1; i < d; ++i) {
    qtd += i * (aux - (aux/10 + 1) + 1);
    aux = aux * 10 + 9;
  }
  qtd += d * (x - (aux/10+1) + 1);
  return {qtd >= k, qtd};
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int q;
  cin >> q;

  while (q--) {
    cin >> k;

    int64_t lo = 1, hi = 1e18, mid = -1, ans = -1;
    while (lo <= hi) {
      mid = lo + (hi - lo) / 2;
      if (f(mid).first) {
        ans = mid;
        hi = mid-1;
      } else {
        lo = mid+1;
      }
    }

    int64_t qtd = f(ans).second;
    string aux = to_string(ans);
    cout << aux[aux.size()-1+k-qtd] << '\n';
  }
}