Time Limit: 1.0 s

Memory Limit: 256.0 MB

Description

You are given an infinite sequence of lowercase English letters built using the following pattern:

abaabaaabaaaabaaaaab ...

This sequence is constructed as follows:

1. Write 1 'a'
2. Then write 1 'b'
3. Then write 2 'a's
4. Then write 1 'b'
5. Then write 3 'a's
6. Then write 1 'b'
7. Then write 4 'a's
8. Then write 1 'b'
9. And so on...

That is, you keep increasing the number of 'a's by 1 each time, and insert a single 'b' after each group of 'a's.

So the sequence starts like this:

a b a a b a a a b a a a a b a a a a a b ...

You are given a positive integer k, and you need to print the k-th character in this infinite sequence (1-based indexing).

Input

• The first line contains an integer t (\(1 ≤ t ≤ 10^5\)) — the number of test cases.
• The next t lines each contain one integer k (\(1 ≤ k ≤ 10^{16}\)) — the position in the sequence to query.

Output

For each test case, output a single character ('a' or 'b') — the character at the k-th position of the sequence.

Sample

7
1
2
3
4
5
4949
1000000

a
b
a
a
b
b
a