题目背景

翻译自 CSES-2431 题。

题目描述

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

你的任务是处理 $q$ 次询问，每次询问会查询字符串第 $k$ 个字符是什么数字。本题字符串编号从 $1$ 开始。

输入格式

第一行输入一个正整数 $q$ 表示询问次数。

接下来有 $q$ 行，每行输入一个整数 $k$ 表示查询。

输出格式

对于每次查询，输出一个数字字符表示答案。

样例

3
7
19
12

7
4
1

说明/提示

$1\le q \le 1000,1\le k \le 10^{18}$。