Bob is a big fan of cubical dices. He builds a dice tower by stacking the dice one on top of the other. A cubical dice and a dice tower are displayed as follows:
Lee was given an integer N. He set out to build a tower with a minimum height, with the sum of points on all of its outer surfaces equaling the provided number N (outer surface: the side surface, the top, and bottom faces).
You had to assist Lee in calculating the minimum number of dice needed to build the tower.
Input format
- The first line contains an integer T denoting the number of test cases.
- The first line of each test case contains an integer N.
Output format
For each test case, print the only integer that denotes the number of dices in the required tower in a new line. If no such tower exists, print −1.
Constraints
1≤T≤1000001≤N≤1000000000
For the first testcase, no such tower exits whose outer surface sum is 1.
For the second testcase, the number of dices required is 1. Therefore, the outer surface sum is (1+2+3+4+5+6)=21.
For the third testcase, the number of dices required is 2. The outer surface of first dice is ([2]+[1+6]+[3+4]). The outer surface of second dice is ([1+6]+[2+5]+[4]).
