#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--)
{
sum = 0;
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+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Ci8qbG9uZyBpbnQgZmlib25hY2NpKGxvbmcgaW50IGEsbG9uZyBpbnQgYixsb25nIGludCBmaWJuLCBsb25nIGludCBzdW0pCnsKCWlmKGZpYm4gPT0gMCkKCQlzdW0gKz0gYTsKCWVsc2UgaWYoZmlibiA9PSAxKQoJCXN1bSs9IGI7CglzdW0rPWZpYm9uYWNjaShhLGIsZmlibi0xLHN1bSkrZmlib25hY2NpKGEsYixmaWJuLTIsc3VtKTsKCXJldHVybiBzdW07Cn0qLwoKCgoKCmludCBtYWluKCkKewoJaW50IHRlc3Q7Cglsb25nIGludCBhLGIsZmlibixtb2RsOwoJc3RhdGljIGxvbmcgaW50IHN1bT0wOwoJbG9uZyBpbnQgYXJyWzEwMDAwMF0gPSB7TlVMTH07CgljaW4gPj4gdGVzdDsKCXdoaWxlKHRlc3QtLSkKCXsKCQlzdW0gPSAwOwoJCWNpbiA+PiBhID4+IGIgPj4gZmlibiA+PiBtb2RsOwoJCS8vY291dCA8PCBmaWJvbmFjY2koYSxiLGZpYm4sc3VtKSVtb2RsPDxlbmRsOwoJCWFyclswXSA9IGE7CgkJYXJyWzFdID0gYjsKCQlmb3IoaW50IGk9MjtpPD0xMDAwMDA7aSsrKQoJCQlhcnJbaV0gPSBhcnJbaS0xXSthcnJbaS0yXTsKCQlmb3IoaW50IGk9MDtpPD1maWJuLTE7aSsrKQoJCQl7c3VtICs9IGFycltpXTsKCQkJc3VtID0gc3VtICVtb2RsOwoJCX0KCQkJCgkJLy9zdW0gPSBzdW0gJSBtb2RsOwoJCQoJCWNvdXQgPDwgc3VtIDw8IGVuZGw7Cgl9CglyZXR1cm4gMDsKfQ==