#include <iostream>
using namespace std;
int main(){
	long long int t, n, k, p, a, b, c, d, e;
	long long N, K;
	cin>>t;
	while(t--){
		cin>>N>>K>>p;
		N++; K++;
		a=1;
		while(K){
			k = K%p;	K = K/p;
			n = N%p;	N = N/p;
			b=1; c=1;
			if(n-k<0){
				a=0;	break;
			}
			if(n-k<k)	k = n-k;
			while(k){
				b = (b*(n+1-k))%p;
				c = (c*k)%p;
				k -= 1;
			}
			d = 1;	e = p-2;
			while(e){
				if(e%2)	d = (d*c)%p;
				c = (c*c)%p;
				e /= 2;
			}
			b = (b*d)%p;
			a = (a*b)%p;
		}
		cout<<a<<endl;
	}
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgbWFpbigpewoJbG9uZyBsb25nIGludCB0LCBuLCBrLCBwLCBhLCBiLCBjLCBkLCBlOwoJbG9uZyBsb25nIE4sIEs7CgljaW4+PnQ7Cgl3aGlsZSh0LS0pewoJCWNpbj4+Tj4+Sz4+cDsKCQlOKys7IEsrKzsKCQlhPTE7CgkJd2hpbGUoSyl7CgkJCWsgPSBLJXA7CUsgPSBLL3A7CgkJCW4gPSBOJXA7CU4gPSBOL3A7CgkJCWI9MTsgYz0xOwoJCQlpZihuLWs8MCl7CgkJCQlhPTA7CWJyZWFrOwoJCQl9CgkJCWlmKG4tazxrKQlrID0gbi1rOwoJCQl3aGlsZShrKXsKCQkJCWIgPSAoYioobisxLWspKSVwOwoJCQkJYyA9IChjKmspJXA7CgkJCQlrIC09IDE7CgkJCX0KCQkJZCA9IDE7CWUgPSBwLTI7CgkJCXdoaWxlKGUpewoJCQkJaWYoZSUyKQlkID0gKGQqYyklcDsKCQkJCWMgPSAoYypjKSVwOwoJCQkJZSAvPSAyOwoJCQl9CgkJCWIgPSAoYipkKSVwOwoJCQlhID0gKGEqYiklcDsKCQl9CgkJY291dDw8YTw8ZW5kbDsKCX0KCXJldHVybiAwOwp9

OAoyMDAwMDAwMDAwMDAgMTAwMDAwMDAwMDAgMgoyMDAwMDAwMDAwIDEyIDUwMDAwCjUwMDAwMDAwMDAwMCAzMDAwMCAxMzAwMDAKNSAyIDMKNiA1IDExCjcgNiAzCjYgNSA3CjYgNSA1

8
200000000000 10000000000 2
2000000000 12 50000
500000000000 30000 130000
5 2 3
6 5 11
7 6 3
6 5 7
6 5 5