You are standing at the point 00 on a coordinate line. Your goal is to reach the point nn. In one minute, you can move by 22 or by 33 to the left or to the right (i. e., if your current coordinate is xx, it can become x−3x−3, x−2x−2, x+2x+2 or x+3x+3). Note that the new coordinate can become negative.
Your task is to find the minimum number of minutes required to get from the point 00 to the point nn.
You have to answer tt independent test cases.
The first line of the input contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases. Then tt lines describing the test cases follow.
The ii-th of these lines contains one integer nn (1≤n≤1091≤n≤109) — the goal of the ii-th test case.
For each test case, print one integer — the minimum number of minutes required to get from the point 00 to the point nn for the corresponding test case.
4
1
3
4
12
2
1
2
4