Problem Description

Today, Soda has learned a sequence whose $n$-th $(n \ge 1)$ item is $3n(n-1)+1$. Now he wants to know if an integer $m$ can be represented as the sum of some items of that sequence. If possible, what are the minimum items needed?

For example, $22 = 19 + 1 + 1 + 1 = 7 + 7 + 7 + 1$.

Input

There are multiple test cases. The first line of input contains an integer $T$ $(1 \le T \le 10^4)$, indicating the number of test cases. For each test case:

There's a line containing an integer $m$ $(1 \le m \le 10^9)$.

Output

For each test case, output $-1$ if $m$ cannot be represented as the sum of some items of that sequence, otherwise output the minimum items needed.

10
1
2
3
4
5
6
7
8
22
10

1
2
3
4
5
6
1
2
4
4