您有 5 种不同类型的硬币，每种硬币的值都等于前 5 个三角形数字之一： 1 、 3 、 6 、 10 和 15 。这些硬币类型非常丰富。您的目标是找到所需的最少数量的硬币，以使它们的总价值恰好为 n。
我们可以证明答案总是存在的。 
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;
const int mod  = 1e9 + 7;
void solve(){
	int n;
	cin>>n;
	int a1[4] = {15,6,3,1};
	int ans = 0;
	if(n%3 == 0){		//如果是3的倍数，则不考虑 10
		for(int i = 0;i < 4; i++){
			ans += n / a1[i];
			n %= a1[i];
		}
	}else{
		int cnt = 0,x = n;	//先考虑10
		while(x){
			cnt += x%10;
			x /= 10;
		}
		int mi = cnt % 3;
		ans = min(mi,n/10);
		n -= ans * 10;
		for(int i = 0;i < 4; i++){
			ans += n / a1[i];
			n %= a1[i];
		}
	}
	cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0 ;
}