F. 机惨

#include <bits/stdc++.h>
using namespace std;
long long seed,mod,w,k;
int rnd()
{
	seed = (1ll * seed * 7 + 13) % mod;
	return seed;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		cin>>seed>>mod>>w>>k;
		long long cur=0,ans=LLONG_MAX;
		int n=1;
		while(1)
		{
			cur+=rnd();
			long long m=ceil(pow(k,1.0/n))-1;
			for(int i=0;i<=n;i++)
			{
				if((long long)(pow(m+1,i)*pow(m,n-i))>=k)
				{
					ans=min(ans,cur+m*w*i+(m-1)*w*(n-i));
					break;
				}
			}
			if((1<<n)>=k)
			{
				break;
			}
			n++;
		}
		cout<<ans<<"\n";
	} 
	return 0;
}