题目描述

考虑一个由所有正整数按递增顺序组成的无限字符串: 12345678910111213141516171819202122232425...

你的任务是处理 q 次查询,每个查询的形式为:字符串中位置 k 上的数字是什么?

输入格式

第一行输入包含一个整数 q :查询的数量。

在此之后,有 q 行描述查询。每行有一个整数 k。字符串中的一个从1开始的位置。

输出格式

对于每个查询,输出相应的数字。

3
7
19
12

7
4
1

数据范围与提示

$1≤q≤1000$

$1≤k≤10^{18}$