Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E2. Numerical Sequence (hard version)

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe only difference between the easy and the hard versions is the maximum value of $$$k$$$.

You are given an infinite sequence of form "112123123412345$$$\dots$$$" 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$$$, $$$\dots$$$, 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 \le q \le 500$$$) — the number of queries.

The $$$i$$$-th of the following $$$q$$$ lines contains one integer $$$k_i$$$ $$$(1 \le k_i \le 10^{18})$$$ — the description of the corresponding query.

Output

Print $$$q$$$ lines. In the $$$i$$$-th line print one digit $$$x_i$$$ $$$(0 \le x_i \le 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.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/18/2019 23:08:37 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|