分治。

在 $b \le 1000$ 时暴力枚举。

当 $b>1000$ 时，$b$ 进制数位不超过 $7$ 位，枚举每一个 $2^7$ 内的二进制位判断是否存在满足条件的即可。

注意防止溢出。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1010,inf=1e18+10;
int calc(int f,int x)
{
	int p=1,ans=0;
	for(int i=0;i<7;i++,p*=x)
	{
		if(f&(1<<i))
		{
			if(ans>inf-p)return inf*2;
			ans+=p;
			f-=(1<<i);
		}
		if(f&&x>(int)(inf/p)+10)return inf*2;
	}
	return ans;
}
void solve()
{
	int n,ans=0;cin>>n;map<int,int>mp;
	for(int i=2;i<=1000;i++)
	{
		int m=n,bk=1;
		while(m)
		{
			if(m%i>1)
			{
				bk=0;
				break;
			}
			m/=i;
		}
		ans+=bk;
	}
	for(int i=1;i<128;i++)
	{
		int l=2,r=1e18,res=2;

		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(calc(i,mid)<=n)l=mid+1,res=mid;
			else r=mid-1;
		}
		if(calc(i,res)==n&&res>1000&&!mp[res])ans++,mp[res]=1;
	}
	cout<<ans<<'\n';
}
signed main()
{
	int t;cin>>t;
	while(t--)solve();
	return 0;
}