## Algorithm

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 n. 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 x, it can become x3�−3x2�−2x+2�+2 or x+3�+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 n.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1t1041≤�≤104) — the number of test cases. Then t lines describing the test cases follow.

The i-th of these lines contains one integer n (1n1091≤�≤109) — the goal of the i-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 n for the corresponding test case.

Example
input
Copy
4
1
3
4
12
output
Copy
2
1
2
4


## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;
while(t--){
int n;
cin>>n;
int ans;
if(n == 1){
ans = 2;
}
else if(n % 3 != 0){
ans = n/3 + 1;
}
else{
ans = n/3;
}
cout<<ans<<endl;
}

}
Copy The Code &

Input

cmd
4
1
3
4
12

Output

cmd
2
1
2
4