The only difference between the easy and the hard versions is the maximum value of k.

You are given an infinite sequence of form "112123123412345..." which consist of blocks of all consecutive positive integers written one after another. The first block consists of all numbers from 1 to 1, the second one — from 1 to 2, the third one — from 1 to 3, ..., the i-th block consists of all numbers from 1 to i. 

So the first 56 elements of the sequence are "11212312341234512345612345671234567812345678912345678910". Elements of the sequence are numbered from one. For example, the 1-st element of the sequence is 1, the 3-rd element of the sequence is 2, the 20-th element of the sequence is 5, the 38-th element is 2, the 56-th element of the sequence is 0.

Your task is to answer q independent queries. In the i-th query you are given one integer k_i. Calculate the digit at the position k_i of the sequence.

Input

The first line of the input contains one integer q (1 ≤ q ≤ 500) — the number of queries.

The i-th of the following q lines contains one integer k_i (1 ≤ k_i ≤ 10^9) — the description of the corresponding query.

Output

Print q lines. In the i-th line print one digit x_i (0 ≤ x_i ≤ 9) — the answer to the query i, i.e. x_i should be equal to the element at the position k_i of the sequence.

Examples

Input


5
1
3
20
38
56


Output


1
2
5
2
0


Input


4
2132
506
999999999
1000000000


Output


8
2
9
8

Note

Answers on queries from the first example are described in the problem statement.
#include <bits/stdc++.h>
long long MAX = -100000000000;
long long MIN = -100000000000;
long long MOD = 1000000007;
long long longlongmax = 9223372036854775807LL;
long long maxormin(long long a, long long b, long long flag) {
  return flag == 1 ? (a > b ? a : b) : (a < b ? a : b);
}
long long overflowcheck(long long a) {
  if (a == 1) {
    return 0;
  } else {
    long long temp = a;
    long long power = 1;
    while (longlongmax / temp > a) {
      temp *= a;
      power++;
    }
    return power + 1;
  }
}
long long merge(long long A[], long long B[], long long left, long long mid,
                long long right) {
  long long count = 0;
  long long n1 = mid - left + 1;
  long long n2 = right - mid;
  long long LA[n1], LB[n1], RA[n1], RB[n2];
  for (long long n = 0; n < n1; n++) {
    LA[n] = A[n + left];
    LB[n] = B[n + left];
  }
  for (long long n = 0; n < n2; n++) {
    RA[n] = A[n + mid + 1];
    RB[n] = B[n + mid + 1];
  }
  long long i = 0, j = 0, k = left;
  while (i < n1 && j < n2) {
    if (LA[i] < RA[j]) {
      A[k] = LA[i];
      B[k] = LB[i];
      i++;
    } else {
      A[k] = RA[j];
      B[k] = RB[j];
      count += n1 - i;
      j++;
    }
    k++;
  }
  while (i < n1) {
    A[k] = LA[i];
    B[k] = LB[i];
    i++;
    k++;
  }
  while (j < n2) {
    A[k] = RA[j];
    B[k] = RB[j];
    j++;
    k++;
  }
  return count;
}
long long mergesort(long long A[], long long B[], long long left,
                    long long right) {
  long long total = 0;
  if (left < right) {
    long long mid = (right - left) / 2 + left;
    total += mergesort(A, B, left, mid);
    total += mergesort(A, B, mid + 1, right);
    total += merge(A, B, left, mid, right);
  }
  return total;
}
long long gcd(long long a, long long b) {
  if (b == 0) {
    return a;
  }
  return gcd(b, b % a);
}
long long numofdigits(long long num) {
  long long total = 0;
  for (long long i = 1; i <= num; i *= 10) {
    total += (num - i + 1);
  }
  return total;
}
long long func(long long num) {
  long long p = 0;
  for (long long i = 0; pow(10, i) <= num; i++) {
    long long sub = 0;
    long long add = 0;
    if (num >= (pow(10, i + 1))) {
      sub += 9 * (pow(10, i)) * ((pow(10, i + 1) - 1) / 9);
      long long big = pow(10, i + 1);
      long long small = pow(10, i);
      add += (i + 1) * (big * (big + 1) / 2 - small * (small + 1) / 2);
      p += add - sub;
    } else if (num < pow(10, i + 1) && num >= pow(10, i)) {
      sub += (num - (pow(10, i)) + 1) * ((pow(10, i + 1) - 1) / 9);
      long long big = num + 1;
      long long small = pow(10, i);
      add += (i + 1) * (big * (big + 1) / 2 - small * (small + 1) / 2);
      p += add - sub;
    }
  }
  return p;
}
int main(int argc, char const *argv[]) {
  long long T = 1;
  scanf("%lld", &T);
  for (long long t = 0; t < T; t++) {
    long long N;
    scanf("%lld", &N);
    long long high = 1e9;
    long long low = 0;
    long long mid = (low + (high - low) / 2);
    long long found = 0;
    while (!found) {
      mid = (low + (high - low) / 2);
      if (func(mid) <= N && func(mid + 1) > N) {
        found = 1;
      } else if (func(mid) > N) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    long long left = N - func(mid);
    if (left == 0) {
      printf("%lld\n", mid % 10);
      continue;
    }
    low = 0;
    high = 1e9;
    found = 0;
    while (!found) {
      mid = (low + (high - low) / 2);
      if (numofdigits(mid) <= left && numofdigits(mid + 1) > left) {
        found = 1;
      } else if (numofdigits(mid) > left) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    long long finally = left - numofdigits(mid);
    if (finally == 0) {
      printf("%lld\n", (mid) % 10);
      continue;
    }
    long long array[5000];
    long long ind = 0;
    long long op = mid + 1;
    while (op) {
      array[ind++] = op % 10;
      op /= 10;
    }
    printf("%lld\n", array[ind - finally]);
  }
  return 0;
}
