这题其实是一道比较好想的题

思考：如果我要增大魔法棒的数量，我的操作是把其中1根变成k²根（k为整数）

实际上增加的量为k²-1

在此前提下，k=1是毫无贡献的，因此我们只需考虑k>1。

k=2时，每次操作相当于将数量增加3。k=3时，每次操作相当于将数量增加8。

我们的数学常识告诉我们：

任意一个数，对3取模以后的结果只能是0或者±1，因此其在平方以后对3取模的结果只能是0或者1。

也就是说一次操作增加的数量可以写成3a-1或者3a的形式。

因此，k>3的时候，每次操作可以等效为整数次k=2的操作和整数次k=3的操作的叠加。

考虑到k=2是最小的有意义的操作，不妨设给定的数为n。对于所有n，我们按对3取模的结果分成三类。我们只需要找到每一类最小成立的那个数，对于同一类的其它数，在基础上进行若干次k=2的操作即可。

1.n%3==1

  • n=1的时候显然成立，因此只要n%3==1只需要输出"Yes"就行。

2.n%3==2

  • 由于一次操作增加的数量只能是3a或者3a-1，所以我们至少要进行两次k=3的操作，然后进行若干次k=2的操作也就是说，最小的输出"Yes"的数是1+8+8=17。对于n<17且n%3==2的情况输出"No"。

3.n%3==0

  • 由于一次操作增加的数量只能是3a或者3a-1，所以我们至少要进行一次k=3的操作，然后进行若干次k=2的操作。也就是说，最小的输出"Yes"的数是1+8=9。对于n<9且n%3==0的情况输出"No"。

分类讨论完成，按结论输出即可。

#include <bits/stdc++.h>
using namespace std;
long long T=1,n,cnt,l;
string s,s1="HBUT";
long long ans;
void solve(){
	cin>>n;
	if(n%3==2&&n<17||n%3==0&&n<9){
        cout<<"No\n";
        return;
    }
    cout<<"Yes\n";
}


int main(){
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}