#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int e=1e3+7;
ll f[e];
ll x,y,a,b,mod;
ll dp[e][e];
int main()
{
     ll t;
     cin>>t;
     while(t--)
     {
         cin>>x>>y>>a>>b>>mod;
         f[1]=1;
         f[2]=1;
         for(ll i=3;i<=500;i++)
         {
            f[i]=(f[i-1]+f[i-2])%mod;
         }
         a=a%mod;
         b=b%mod;
         for(ll i=1;i<=x;i++)
         {
             dp[i][0]=i;
         }
         for(ll i=1;i<=y;i++)
         {
             dp[0][i]=i;
         }
         for(ll i=1;i<=x;i++)
         {
             for(ll j=1;j<=y;j++)
             {
                 dp[i][j]=(a*dp[i-1][j]+b*dp[i][j-1]+f[__gcd(i,j)])%mod;
             }
         }
         cout<<dp[x][y]%mod<<endl;
     }
}