The "BHAI Group" Of IIIT Allahabad is Famous For Many Things, Leading in Every Field Of College Activity

So One Day The Leader Of Bhai Group decided to smoke C(N) cigarettes each day:

• F(N) = 34^N + (30 × N) + 32
• C(N) = F(N) mod 11, where x mod y is the remainder obtained by dividing x by y.

But Bhai Group's Leader's Girlfriend wants that he doesn't smoke any cigarettes, so she made a modification:

• F(N) = 34^N + (30 × N) + (32 + M)
• C(N) = F(N) mod 11

Input

First line of each test case is an integer T, total number of test cases. Next T lines contains a single integer N.

Output

Print the minimum value of M in single line for each test case.

Constraints

1 ≤ T ≤ 10⁶

1 ≤ N ≤ 10¹⁸

Example

Input:
2
1
2
Output:
3
6

Explanation

For N = 1, F(N) = 34 + 30 + 32 = 96. So, M = 3, now C(N) = 99 mod11 = 0.

For N = 2, F(N) = 1156 + 60 + 32 = 1248. So, M = 6, now C(N) = 1254 mod11 = 0

Problem Credits : IIIT Allahabad HE Club