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.

import java.util.Scanner;

public class Main {
	/**
	 * a[i]表示第长度为I的底层的所有。
	 * 第层差距为2；
	 */
	private static long[] a ;//a[i]表示到第i层结束有多少个数字。
	private static long[] base10 ;
	private static int MAXN = 9;
	private static long[] c ;//到层结束有多少个数字。
	
	private static  int getlog10(long i){
		return (int)Math.round(Math.floor(Math.log10((double)i))) +1;
	}
	
	public static  void init(){
		a = new long[MAXN+1];
		base10 = new long[MAXN+1];
		base10[0]=1l;base10[1] = 10l;
		c = new long[MAXN+1];
		c[0] = 0;
		c[1] = 9l;
		
		for(int i=2;i<=MAXN;i++){
			base10[i] = base10[i-1]*10;
			c[i] = c[i-1] + base10[i-1]*i*9;
		}
		
		for(int i = 1; i<=MAXN; i++){
			long a1 = bN( base10[i-1]  );
			long aN = bN(base10[i] -1);
			a[i] = a[i-1] +  sameDiffSum(a1, aN, i);
			
		}
	}
	
	public static  int find(long k){
		int level = 1;
		for(int i=1;i<=MAXN;i++){
			if( k <= a[i] ) {
				level = i ;
				break;
			}
		}
		long left = k - a[level-1];
//		//落在第level层，这层是等差数列。b[base10[level-1],b[base10[level-1]+1]=b[base10[level-1]+d,b[base10[level-1]+2]...,b[base10[level-1]+N]+Nd;
		//假设落在n>=2。(a1+a1+(n-1)*d  ) *n /2  = S>=left 也就是 left<= a1*n + n*(n-1)/2 *d  && left>a1*(n-1)+(n-1)*(n-2)/2*d;
		long a1 = bN( base10[level-1] );
		long d = level;
		long num =  evluate(left, a1, d);
		long n = base10[level-1] + (num -1)*d;
		//找到落到1....n;也就b[base10[level-1]]+(b[base10[levlel-1]]+d)+.....b[base10[level-1]+(N-2)*d.     b[base10[level-1]{}
		if( num >= 2){
			left = left - sameDiffSum(a1, a1+(num-2)*d, d); 
		}
//		if (sameDiffSum(a1, a1+(N+1)d, d) > left && sameDiffSum(a1, a1+Nd, d) >= left )
		return inWhichN(left);
	}
	
	/**
	 * 
	 * 1...N  偏移量为num;
	 * 
	 * @param num
	 * @return 
	 */
	public static int inWhichN(long num){
		int depth = -1;
		for(int  i=1;i<=MAXN;i++){
			if( num<= c[i]	) {
				depth = i;
				break;
			}
		}
		//落在depth层上面就是数字个数是depth的层次上面.应该是第depth上面的位置。
		long left  = num  - c[depth-1] ;
	//	depth*x+y = left;
		long n = left/depth ;
		long c = left%depth;
		
		long  t  =  base10[depth-1]  ;
		if( n > 0 ){
			t =  base10[depth-1]  + n - 1;
		}
		if( c > 0 ) {
			t = t + 1;
			String s = String.valueOf(t);
			return s.charAt((int)c-1)-'0';
		}else{
			String s = String.valueOf(t);
			return s.charAt(s.length()-1)-'0';
		}
	}

	/**
	 * 
	 * 
	 * 
	 * @param left
	 * @param a1
	 * @param d
	 * @return
	 */
	public static long evluate(long left,long a1,long d){
		if( left  <= a1) {
			return 1;
		}
		
		double a = (double)d/2 ;
		double b = (double)a1 - a;
		double c = (double)left*(-1);
		
		double x = ( Math.sqrt(b*b-4*a*c) - b) / (2*a);
		
		long n1 = (long)Math.ceil(x);
		long n0 = Math.max( (long)Math.floor(x),1);
		
		long sum = sameDiffSum(a1, a1+(n0-1), d);
		
		if( sum >= left ) {
			return n0;
		}
		return n1;
	}
	
	/**
	 * 
	 * @param n
	 * @return 表示从b1,b2,b3,...,bn的序列的数字个数。
	 */
	public static long aN(long  n){
		long digitNum = getlog10(n);
		long sum = 0l;
		long start = 1l;
		
		for( long  i = 1; i<= digitNum-1; i++ ){

			long a1 = bN(start);
			long aN = bN(start*10l-1);
			
			sum =  sum +  sameDiffSum(a1, aN, i);
			
			start = start*10;
		}
		
	       sum = sum + sameDiffSum( bN(start), bN(n), digitNum);	       
		
		return sum;
	}
	

	private static long sameDiffSum(long a1, long aN, long d) {
		long N = ( aN - a1 ) / d + 1;
		long tmp =   ( a1 + aN ) * N / 2;
		return tmp;
	}
	
	/**
	 * 
	 * @param n
	 * @return  [1,2,3,4,..n]的数字个数
	 */
	public static long  bN(long n){
		int digitNum = getlog10(n);
		long sum = 0l;

		for(int i=1;i<=digitNum-1;i++){
			sum = sum  +  base10[i-1]*9*i;
		}
		sum =  sum + ( n - base10[digitNum-1] + 1) * digitNum; 
		return sum;
	}
	
	
	
	public static void test(){
		System.out.println(bN(1234));
		for(int i = 1;i<=100;i++){
			System.out.println("b["+i+"]="+bN(i)+";a["+i+"]="+aN(i));
		}
	}
	
	public static void main(String[] args) {
		init();
//		test();
		Scanner in = new Scanner(System.in);
		int q = in.nextInt();
		
		for(int cas=1;cas<=q;cas++){
			long k = in.nextLong();
			
			System.out.println(find(k));
		}
		
	}
}
