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^{18}) — 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
999999999999999999
1000000000000000000


Output


8
2
4
1

Note

Answers on queries from the first example are described in the problem statement.
import java.util.*;
import java.io.*;
import java.math.*;
public class Es5
{
    static IO io = new IO();
    public static void main(String[] args)
    {
		int T = io.getInt();
		while(T-->0){
			long n = io.getLong()-1;
			
			int pos = bound(n, true);
			n = n-len2(pos);
			
			int tmp = 1;
			char sol = 0;
			//io.println(n);
			int pos2 = bound2(n, true);
			n = n-len(pos2);
			io.println(((pos2+1)+"").charAt((int)n));
		}
		
        io.close();
    }
	
	
	static long len(long i){
		long sol = 0;
		long nines = 0;
		long count = 0;
		long tmp = i;
		while(tmp > 0){
			sol += i;
			sol -= nines;
			tmp = tmp/10;
			count++;
			nines = power(10, count) - 1;
		}
		return sol;
	}
	
	static long len2(long n){
		int dig = 0;
		long pow = 1;
		BigInteger sol = new BigInteger("0");
		while(dig <= Math.log10(n)){
			sol = sol.add((BigInteger.valueOf(dig+1).multiply(BigInteger.valueOf(n-pow+1).multiply(BigInteger.valueOf(n-pow+2)))).divide(BigInteger.valueOf(2)));
			pow = 10*pow;
			if(n-pow+1 >= 0)
				sol = sol.subtract((BigInteger.valueOf(dig+1).multiply(BigInteger.valueOf(n-pow+1).multiply(BigInteger.valueOf(n-pow+2)))).divide(BigInteger.valueOf(2)));
			
			dig++;
		}
		return sol.longValue();
	}
	 static long power(long x, long y) 
    { 
        long res = 1;       
        while (y > 0) 
        { 
            if((y & 1)==1) 
                res = (res * x); 
 
            y = y >> 1;  
            x = (x * x);  
        } 
        return res; 
    }
	
	static int bound(long element, boolean lower) //true: lower_bound, false: upper_bound
	{	
		int first = 0;
		int last = 1000000000;
		int mid;
		while (first < last) {
			mid = first + ((last - first) >> 1); 
			long dat = len2(mid);
			if ((lower && dat < element) || (!lower && dat <= element)) 
				first = mid + 1; 
			else 
				last = mid;
		}
		if(len2(first) != element)
			return first-1;
		return first;
	}
	static int bound2(long element, boolean lower) //true: lower_bound, false: upper_bound
	{	
		int first = 0;
		int last = 1000000000;
		int mid;
		while (first < last) {
			mid = first + ((last - first) >> 1); 
			long dat = len(mid);
			if ((lower && dat < element) || (!lower && dat <= element)) 
				first = mid + 1; 
			else 
				last = mid;
		}
		if(len(first) != element)
			return first-1;
		return first;
	}
}



class IO extends PrintWriter {
	public IO() {
        super(new BufferedOutputStream(System.out));
        r = new BufferedReader(new InputStreamReader(System.in));
    }

    public IO(String fileName) {
        super(new BufferedOutputStream(System.out));
        try{
            r = new BufferedReader(new FileReader(fileName));
        } catch (FileNotFoundException e) {
            this.println("File Not Found");
        }
    }

    public boolean hasMoreTokens() {
        return peekToken() != null;
    }

    public int getInt() {
        return Integer.parseInt(nextToken());
    }

    public double getDouble() {
        return Double.parseDouble(nextToken());
    }

    public long getLong() {
        return Long.parseLong(nextToken());
    }

    public String getWord() {
        return nextToken();
    }

	public String getLine(){
        try{
            st = null;
            return r.readLine();
        }
        catch(IOException ex){}
        return null;
    }
	

    private BufferedReader r;
    private String line;
    private StringTokenizer st;
    private String token;

    private String peekToken() {
        if (token == null)
            try {
                while (st == null || !st.hasMoreTokens()) {
                    line = r.readLine();
                    if (line == null) return null;
                    st = new StringTokenizer(line);
                }
                token = st.nextToken();
            } catch (IOException e) { }
        return token;
    }

    private String nextToken() {
        String ans = peekToken();
        token = null;
        return ans;
    }
}
