//
//  YetAnotherCoinProblem.cpp
//  
//
//  Created by Krish Narsaria on 23/12/24.
//
#include <bits/stdc++.h>
#include <string.h>
using namespace std;
#define ll long long
 
void solve(){int n,sum;
cin>>n;int ans=1e9;
	for(int i=0;i<=2;i++){
		for(int j=0;j<=1;j++){
			for(int k=0;k<=4;k++){
				for(int l=0;l<=2;l++){
					sum=i+3*j+6*k+10*l;
					if(sum<=n && !((sum-n)%15)){ans=min(i+j+k+l+(n-sum)/15,ans);}
				}
			}
		}
	}
cout<<ans<<endl;}
 
int main() {
	int t;
	cin>>t;
	while(t--){solve();}
	return 0;
}
 

Ly8KLy8gIFlldEFub3RoZXJDb2luUHJvYmxlbS5jcHAKLy8gIAovLwovLyAgQ3JlYXRlZCBieSBLcmlzaCBOYXJzYXJpYSBvbiAyMy8xMi8yNC4KLy8KI2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBsbCBsb25nIGxvbmcKCnZvaWQgc29sdmUoKXtpbnQgbixzdW07CmNpbj4+bjtpbnQgYW5zPTFlOTsKCWZvcihpbnQgaT0wO2k8PTI7aSsrKXsKCQlmb3IoaW50IGo9MDtqPD0xO2orKyl7CgkJCWZvcihpbnQgaz0wO2s8PTQ7aysrKXsKCQkJCWZvcihpbnQgbD0wO2w8PTI7bCsrKXsKCQkJCQlzdW09aSszKmorNiprKzEwKmw7CgkJCQkJaWYoc3VtPD1uICYmICEoKHN1bS1uKSUxNSkpe2Fucz1taW4oaStqK2srbCsobi1zdW0pLzE1LGFucyk7fQoJCQkJfQoJCQl9CgkJfQoJfQpjb3V0PDxhbnM8PGVuZGw7fQoKaW50IG1haW4oKSB7CglpbnQgdDsKCWNpbj4+dDsKCXdoaWxlKHQtLSl7c29sdmUoKTt9CglyZXR1cm4gMDsKfQo=

MTQKMQoyCjMKNQo3CjExCjEyCjE0CjE2CjE3CjE4CjIwCjk4CjQwMjkzMTMyOAo=

14
1
2
3
5
7
11
12
14
16
17
18
20
98
402931328