∞

题号：NC24432
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 64 M，其他语言128 M
64bit IO Format: %lld

题目描述

∞, the infinity. It's one of the most complex math symbols. How does it mean? The mathematicians argued for many years. But luckily, the principle of infinity is stable now.

Ramen is doing some boring works on a kind of number string $S_n$ . To produce $S_n$ , write down all numbers from 1 to n in ascending order, then concatenate them directly. For example, $S_7=1234567$ and $S_{15}=123456789101112131415$ .

Especially, the infinity number string is: $S_{\infty} = 12345678910111213\cdots$ .

Ramen likes infinity, but he is bad at counting. He wants to know what the digit is at the position p in the infinity number string $S_{\infty}$ . Can you help him to solve this complex problem?

输入描述:

The input contains multiple test cases.

The first line is an integer T(1 <= T <= 100000), which represents the number of test cases.

Each of the next T lines contains an integer p(1 <= p <= 1e18), represents the position has been asked.

输出描述:

For each test case, output the digit at position p in  in one single line.

示例1

输入

复制

5
1
10
19
66
1000000000000000000

输出

复制

说明

The subsequence of  from 60 to 70 is:


It's apparent that it's 3 when p=66.