#include<stdio.h>
#include<string.h>
int main()
{
int t,a,b,i,j,k,x,y,sum1,sum2;
long long z;
char c[34],d[34];
scanf("%d",&t);
while(t--)
{
scanf("%s %d %s %d",c,&a,d,&b);
x=strlen(c);
y=strlen(d);
for(i=x-1,j=0,sum1=0;i>=0;i--,j++)
{
if( (c[i]<='z' && c[i]>='a') )
{
c[i]=c[i]-'a'+36;
}
if( (c[i]<='Z' && c[i]>='A') )
{
c[i]=c[i]-'A'+10;
}
if( (c[i]<=57 && c[i]>=48) )
{
c[i]=c[i]-48;
}
if(c[i]!='-')
{
for(z=a,k=0;k<=j;k++)
{
if(j==0){
z=1;
}else {
z*=a;
}
}
if(z==1){
sum1+=c[i]z;
} else {
sum1+=z/a/ac[i];
}
}
if(i==0)
{
if(c[0]=='-')
{
sum1=-sum1;
}
}
}
for(i=y-1,j=0,sum2=0;i>=0;i--,j++)
{
if( (d[i]<='z' && d[i]>='a') )
{
d[i]=d[i]-'a'+36;
}
if( (d[i]<='Z' && d[i]>='A') )
{
d[i]=d[i]-'A'+10;
}
if( (d[i]<=57 && d[i]>=48) )
{
d[i]=d[i]-48;
}
if(d[i]!='-')
{
for(z=b,k=0;k<=j;k++)
{
if(j==0){
z=1;
}else {
z*=b;
}
}
if(z==1){
sum2+=d[i]*z;
} else {
sum2+=z/b/b*d[i];
}
}
if(i==0)
{
if(d[0]=='-')
{
sum2=-sum2;
}
}
}
printf("%d\n",sum1+sum2);
}
return 0;
}