#include<bits/stdc++.h>
#define ll long long
#define re register
#define ull unsigned ll
using namespace std;
inline ll read(){
	ll res=0ll,f=1;
	char c;
	for(;(c=getchar())<'0'||c>'9';c=='-'?f=-f:0);
	while(c>='0' && c<='9') res=(res<<1) + (res<<3) + c-'0',c=getchar();
	return res*f;
}
inline ll Max(re ll x,re ll y){return x>y?x:y;}
inline ll Min(re ll x,re ll y){return x<y?x:y;}
inline void cmax(re auto &x,re auto y){x=Max(x,y);}
inline void cmin(re auto &x,re auto y){x=Min(x,y);}
/*-----------------*/
ll l,r,a,c;
ull b;
ll num[20],k,ans;
inline ull qpow(re ull x,re ull y){
	ull sum=1,now=x%b;
	while(y){
		if(y&1) sum=sum*now%b;
		y>>=1,now=now*now%b;
	}
	return sum;
}
inline ll f(re ll x){
	if(x<0) return 0;
	ll p=0;k=0;
	while(x) num[++k]=(x%10),x/=10;
	for(re int i=1;i<=k;i++) p=p*10+num[i];
	return p;
}
int main(){
	int T;T=read();
	while(T--){
		l=read();r=read();ans=0;
		a=read();b=read();c=read();
		for(re ll i=0;i<b;i++){
			if((ull)i%10==0) continue;
			for(re ll x=f(i);f(x-c)<=r;x*=10){
				if(x-c<0) continue;
				if((ull)(x-c)%10==0) continue;
				for(re ll y=f(x-c);y<=r;y=y*10){
					if(y<l) continue;
					if(qpow(y,a)==i) ans++;
				}
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}