Find Digit in Infinite Concatenated Sequence

Given an infinite sequence \(A\) where each element is defined as \(A_i = \overline{1\underbrace{0\dots0}_{i-1}}\) (i.e. \(A_1 = 1\), \(A_2 = 10\), \(A_3 = 100\), etc.), an infinite sequence \(B\) is constructed by concatenating all \(A_i\) together: \(B = \overline{A_1A_2A_3\dots}\). For example, the beginning of \(B\) is:

1101001000\dots

Your task is to determine the digit at a specified position in the sequence \(B\).

Note: The positions are 1-indexed. Each \(A_i\) is a number starting with 1 followed by \(i-1\) zeros. Thus, if the digit lies at the first position of some \(A_i\), it will be 1; otherwise it will be 0.

The problem can be solved by first finding the block \(A_m\) in which the \(n\)-th digit falls. Since the length of \(A_i\) is \(i\), the total number of digits up to \(A_m\) is \(\frac{m(m+1)}{2}\). Let \(m\) be the smallest integer such that \(\frac{m(m+1)}{2} \ge n\). The position of the digit within \(A_m\) is then \(p = n - \frac{(m-1)m}{2}\). If \(p = 1\), the digit is 1; otherwise, it is 0.

inputFormat

The input begins with a single integer \(T\) representing the number of queries. Each of the following \(T\) lines contains one integer \(n\), the position in the sequence \(B\) (1-indexed), for which you need to determine the digit.

Input Format:

T
n_1
n_2
... 
 n_T

outputFormat

For each query, output a single digit (either '1' or '0') on a separate line.

Output Format:

digit_1
 digit_2
 ... 
 digit_T

sample

1
1

1