Description

给出单个正整数$i$ ，编写程序以找到位于数字组$S_1 , S _2 , …, S_k$ 序列中第$i$ 位上的数字。每个组$S_k$ 都由一系列正整数组成，范围为$1～k$ ，一个接一个地写入。序列的前$80$位数字如下：

Input

第$1$行包含一个整数$t （1≤t ≤10）$，表示测试用例的数量。每个测试用例后都跟一行，包含单个整数$i （1≤i ≤2, 147,483, 647）$。

Output

对每个测试用例，都单行输出第$i$ 位上的数字。

Samples

2
8
3

2
2