Digo and Sharry like to play with numbers and sequences. They decide to write an infinite sequence. For this they start by choosing a number each. They start making the sequence by following these rules:

1. Digo writes his number on a piece of paper. This is the 0th number of the sequence.
2. Then Sharry writes his number on the paper, as many times as Digo’s number. e.g. if Digo wrote 2, then Sharry would write his number 2 times, making the total sequence of length 3.
3. Then Digo writes his number on the paper, which becomes the next element of the sequence.
4. Then Sharry writes his number as many times as the number indexed 1 in the sequence.
5. Then Digo writes his number on the paper, which becomes the next element of the sequence.
6. Then Sharry writes his number as many times as the number indexed 2 in the sequence.
... and the cycle goes on.

Now Digo starts to feel that the sequence that they are generating is very trivial. He claims he can tell the digit at the nth place without having to play the game. So Sharry challenges him to tell the digit which will come at the nth place.

Help Digo complete Sharry's challenge.

It is given that Digo chooses 4 as his number and Sharry chooses 5 as his number.

Input

First line of the input contains an integer T - the number of test cases.

T lines follow, each containing an integer N.

Output

Print T lines. For every test case, print the digit that appears in the Nth place.

Constraints

1 < T < 100

0 <= N < 1000000000

Sample

Input
3
0
4
7

Output
4
5
5

Explanation

The sequence is 4, 5, 5, 5, 5, 4, 5, 5, 5, 5, 5 ...