#include<iostream>
using namespace std;
/*long int fibonacci(long int a,long int b,long int fibn, long int sum)
{
if(fibn == 0)
	sum += a;
else if(fibn == 1)
	sum+= b;
sum+=fibonacci(a,b,fibn-1,sum)+fibonacci(a,b,fibn-2,sum);
return sum;
}*/
 
 
 
 
 
int main()
{
int test;
long int a,b,fibn,modl;
static long int sum=0;
long int arr[100000] = {NULL};
cin >> test;
while(test--)
{
	cin >> a >> b >> fibn >> modl;
	//cout << fibonacci(a,b,fibn,sum)%modl<<endl;
	arr[0] = a;
	arr[1] = b;
	for(int i=2;i<=100000;i++)
		arr[i] = arr[i-1]+arr[i-2];
	for(int i=0;i<=fibn-1;i++)
		{sum += arr[i];
		sum = sum %modl;
	}
 
	//sum = sum % modl;
 
	cout << sum << endl;
}
return 0;
}

I2luY2x1ZGU8aW9zdHJlYW0+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Ci8qbG9uZyBpbnQgZmlib25hY2NpKGxvbmcgaW50IGEsbG9uZyBpbnQgYixsb25nIGludCBmaWJuLCBsb25nIGludCBzdW0pCnsKaWYoZmlibiA9PSAwKQoJc3VtICs9IGE7CmVsc2UgaWYoZmlibiA9PSAxKQoJc3VtKz0gYjsKc3VtKz1maWJvbmFjY2koYSxiLGZpYm4tMSxzdW0pK2ZpYm9uYWNjaShhLGIsZmlibi0yLHN1bSk7CnJldHVybiBzdW07Cn0qLwoKCgoKCmludCBtYWluKCkKewppbnQgdGVzdDsKbG9uZyBpbnQgYSxiLGZpYm4sbW9kbDsKc3RhdGljIGxvbmcgaW50IHN1bT0wOwpsb25nIGludCBhcnJbMTAwMDAwXSA9IHtOVUxMfTsKY2luID4+IHRlc3Q7CndoaWxlKHRlc3QtLSkKewoJY2luID4+IGEgPj4gYiA+PiBmaWJuID4+IG1vZGw7CgkvL2NvdXQgPDwgZmlib25hY2NpKGEsYixmaWJuLHN1bSklbW9kbDw8ZW5kbDsKCWFyclswXSA9IGE7CglhcnJbMV0gPSBiOwoJZm9yKGludCBpPTI7aTw9MTAwMDAwO2krKykKCQlhcnJbaV0gPSBhcnJbaS0xXSthcnJbaS0yXTsKCWZvcihpbnQgaT0wO2k8PWZpYm4tMTtpKyspCgkJe3N1bSArPSBhcnJbaV07CgkJc3VtID0gc3VtICVtb2RsOwoJfQoJCQoJLy9zdW0gPSBzdW0gJSBtb2RsOwoJCgljb3V0IDw8IHN1bSA8PCBlbmRsOwp9CnJldHVybiAwOwp9

MgoyIDIgMTAgMjEKMSAzIDEwIDIx

2
2 2 10 21
1 3 10 21