A. 2-3 Moves

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

Input

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.

Output

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.

Example

input

Copy

4

1

3

4

12

output

Copy

2
1
2
4

解题说明：水题，此题找规律即可，注意区分n=1的情况。

#include
int main()
{
	int t, n;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &n);
		if (n == 1)
		{
			printf("2\n");
		}
		else
		{
			printf("%d\n", ((n - 1) / 3) + 1);
		}
	}
	return 0;
}