#include<cstdio>#include<cstring>#include<map>#include<iostream>using namespace std;const int N = 10005;typedef long long ll;ll ext_gcd(ll a, ll b, ll &x, ll &y){int t, d;if (b == 0) { x = 1; y = 0; return a; }d = ext_gcd(b, a % b, x, y);t = x;x = y;y = t - a / b*y;return d;}ll Invmod(int a,int n){ll x,y;if (ext_gcd(a,n,x,y)!=1)return -1;return (x%n+n)%n;}char s[N];ll h[N];map<ll,int>lzs;int main(){int P,MOD,v,T;scanf("%d",&T);getchar();while(T--){lzs.clear();gets(s);scanf("%d%d%d",&P,&MOD,&v);getchar();int ni=Invmod(P,MOD);int len=strlen(s);for(int i=1;i<=len;i++){h[i]=(h[i-1]*P+s[i-1])%MOD;}int ret=0;ll nv=1;for(int i=0;i<=len;i++){ll nw=h[i]*nv%MOD,tv=v*nv%MOD;ll need=nw-tv;if(need<0)need+=MOD;if(lzs.find(need)!=lzs.end())ret+=lzs[need];lzs[nw]++;nv=nv*ni%MOD;}printf("%dn",ret);}return 0;}
