Today, Soda has learned a sequence whose n-th (n≥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≤T≤104), indicating the number of test cases. For each test case:
There's a line containing an integer m (1≤m≤109).
There's a line containing an integer m (1≤m≤109).
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.
Sample Input
10
1
2
3
4
5
6
7
8
22
10
Sample Output
1
2
3
4
5
6
1
2
4
4
Source
/*
对于(n-1)%6 + 1还没想明白，等脑子清醒了再搞。。。
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX = 20000;
int a[MAX];
void solve()
{
for(int i = 0; i <= MAX; i++)
a[i] = 3 * i * (i-1) + 1;
}
int solve(int n)
{
int ans = n % 6;
if(ans == 1){
for(int i = 0 ; i <= MAX; i++){
if(a[i] == n) return 1;
}
return 7;
}
if(ans == 2){
int j = MAX - 1;
for(int i = 1; i <=j; i++){
while(a[i] + a[j] > n)
j--;
if(a[i] + a[j] == n)
return 2;
}
return 8;
}
return (n - 1) % 6 + 1;
}
int main()
{
int T, n;
scanf("%d", &T);
while(T--){
scanf("%d", &n);
printf("%d
", solve(n));
}
return 0;
}