#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll** matmul(ll** v1,ll** v2,ll M)
{
ll **c;
c=(ll **)calloc(2,sizeof(long long));
c[0]=(ll*)calloc(2,sizeof(long long));
c[1]=(ll*)calloc(2,sizeof(long long));
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
for(int k=0;k<2;k++)
{
c[i][j]=(c[i][j]+v1[i][k]*v2[k][j])%M;
}
}
}
return c;
}
ll** matpow(ll **v,ll n,int M) //variable pointer..
{
ll **v2;
v2=(ll **)calloc(2,sizeof(long long));
v2[0]=(ll*)calloc(2,sizeof(long long));
v2[1]=(ll*)calloc(2,sizeof(long long));
for(int i=0;i<n;i++)
{
v2[i][i]=1;
}
while(n)
{
if(n%2)
v2=matmul(v2,v,M);
n/=2;
v=matmul(v,v,M);
}
return v2;
}
int main()
{
int t,m;
ll a,n,xx=1;
cin>>t;
for(int i=0;i<t;i++)
{
cin>>a>>n>>m;
ll **v;
v=(ll**)calloc(2,sizeof(long long));
v[0]=(ll*)calloc(2,sizeof(long long));
v[1]=(ll*)calloc(2,sizeof(long long));
ll temp=a;int dig=0;
while(temp!=0)
{
dig++;
xx*=10;
temp/=10;
}
v[0][0]=xx%m;
v[0][1]=1;
v[1][0]=0;
v[1][1]=1;
v=matpow(v,n-1,m);
cout<<((v[0][0]+v[0][1])%m*(a%m))%m<<endl;
xx=1;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwogCmxsKiogbWF0bXVsKGxsKiogdjEsbGwqKiB2MixsbCBNKQp7CglsbCAqKmM7CgljPShsbCAqKiljYWxsb2MoMixzaXplb2YobG9uZyBsb25nKSk7CgljWzBdPShsbCopY2FsbG9jKDIsc2l6ZW9mKGxvbmcgbG9uZykpOwoJY1sxXT0obGwqKWNhbGxvYygyLHNpemVvZihsb25nIGxvbmcpKTsKCWZvcihpbnQgaT0wO2k8MjtpKyspCgl7CgkJZm9yKGludCBqPTA7ajwyO2orKykKCQl7CgkJCWZvcihpbnQgaz0wO2s8MjtrKyspCgkJCXsKCQkJCWNbaV1bal09KGNbaV1bal0rdjFbaV1ba10qdjJba11bal0pJU07CgkJCX0KCQl9Cgl9CglyZXR1cm4gYzsKfQpsbCoqIG1hdHBvdyhsbCAqKnYsbGwgbixpbnQgTSkgLy92YXJpYWJsZSBwb2ludGVyLi4KewoJCglsbCAqKnYyOwoJdjI9KGxsICoqKWNhbGxvYygyLHNpemVvZihsb25nIGxvbmcpKTsKCXYyWzBdPShsbCopY2FsbG9jKDIsc2l6ZW9mKGxvbmcgbG9uZykpOwoJdjJbMV09KGxsKiljYWxsb2MoMixzaXplb2YobG9uZyBsb25nKSk7Cglmb3IoaW50IGk9MDtpPG47aSsrKQoJewoJCXYyW2ldW2ldPTE7Cgl9Cgl3aGlsZShuKQoJewoJCWlmKG4lMikKCQkJdjI9bWF0bXVsKHYyLHYsTSk7CgkJbi89MjsKCQl2PW1hdG11bCh2LHYsTSk7Cgl9CglyZXR1cm4gdjI7Cn0KaW50IG1haW4oKQp7CglpbnQgdCxtOwoJbGwgYSxuLHh4PTE7CgljaW4+PnQ7Cglmb3IoaW50IGk9MDtpPHQ7aSsrKQoJewoJCWNpbj4+YT4+bj4+bTsKCQlsbCAqKnY7CgkJdj0obGwqKiljYWxsb2MoMixzaXplb2YobG9uZyBsb25nKSk7CgkJdlswXT0obGwqKWNhbGxvYygyLHNpemVvZihsb25nIGxvbmcpKTsKCQl2WzFdPShsbCopY2FsbG9jKDIsc2l6ZW9mKGxvbmcgbG9uZykpOwoJCQoJCQkKCQlsbCB0ZW1wPWE7aW50IGRpZz0wOwoJCXdoaWxlKHRlbXAhPTApCgkJewoJCQlkaWcrKzsKCQkJeHgqPTEwOwoJCQl0ZW1wLz0xMDsKCQl9CgkJdlswXVswXT14eCVtOwoJCXZbMF1bMV09MTsKCQl2WzFdWzBdPTA7CgkJdlsxXVsxXT0xOwoJCXY9bWF0cG93KHYsbi0xLG0pOyAKCQljb3V0PDwoKHZbMF1bMF0rdlswXVsxXSklbSooYSVtKSklbTw8ZW5kbDsKCQkKCQl4eD0xOwoJfQoJcmV0dXJuIDA7Cn0=