首先说一下。N*（N-1）/2为三角形数，随意一个自然数都最多可由三个三角形数表示。

对于，对于给定的要求值 V, 那么其一组解可表示为 V = 6*（K个三角形数的和）+K； 即随意由k个数组成的解 都有 （V-K）%6==0;

那么仅仅须要找到最小的K（1,2须要特判，结论最小值为3）；

在对2进行特判时候，能够从两端到中间的线性扫描来做。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <map>

using namespace std;

typedef long long LL;

const int N = 100005;

int n,f[N];

void init(){

    for(int i=1;;i++){

          int num= 3*i*(i-1)+1;

          f[i]=num;

          if(num>1e9){

              n=i;

              break;

          }

    }

}

int get(int v){

  int p = lower_bound(f+1,f+1+n,v)-f;

  return f[p]==v;

}

int find_(int v){

  int l=1,r=n;

  while(l<=r){

     if(f[l] + f[r] < v) return 0;

     while(l<=r){

         if(f[l]+f[r] < v) {r++; break;}

         else if(f[l]+f[r]==v) return 1;

         else r--;

     }

     l++;

  }

  return 0;

}

int main()

{

    init();

    int T;

    scanf("%d",&T);

    while(T--){

        int k; scanf("%d",&k);

        if(get(k)) printf("1\n");

        else{

            int ok=0;

            if((k-2)%6 == 0){

                if(find_(k)) {ok=1;}

            }

            if(ok) printf("2\n");

            else {

                 for(int i=3;i<=8;i++){

                      if((k-i)%6 == 0){

                           printf("%d\n",i);

                           break;

                      }

                 }

            }

        }

    }

    return 0;

}