seuOJ527 - 机惨

题目描述

Ambition 出去买饮料了！擅长光速机惨的 nkxjlym 显然不会错过这次机会，他决定进行他的机惨计划，用字符 a 填满 Ambition 电脑里的记事本！

nkxjlym 打开了 Ambition 电脑里的记事本，输入了一个字符 a。接下来，他有两种操作：

  1. 花费 vv 秒，全选所有记事本里的文字，复制，并且将光标移动到文本的尾部。
  2. 花费 ww 秒，按下粘贴键，将他最新一次复制的所有文本粘贴到记事本中已有文本的末尾。

nkxjlym 知道，要让 Ambition 的电脑死机，至少要在记事本中输入 kk 个字符。

不幸的是，Ambition 走前，为了防止 nkxjlym 机惨他，在电脑里写了一段程序，使得 nkxjlym 进行操作1的时间不是一个固定值，而是 v=rnd()v=rnd()，其中 rnd 是一段随机数程序，每一次调用都会返回一个新的值。

Ambition 马上就要回来了，nkxjlym 想要知道，假如以最优顺序按键，让 Ambition 的电脑死机的时间最短是多少。

以下是这段随机数程序的 C++ 版本和 py 版本。

int rnd()
{
	seed = (1ll * seed * 7 + 13) % mod;
	return seed;
}

def rnd():
    global seed
    seed = (seed * 7 + 13) % mod
    return seed

输入格式

第一行，一个整数 t(1≤t≤104)t(1\le t\le 10^4)，代表数据组数。

对于每组数据，输入仅有一行四个整数 seed,mod,w,k(0≤seed≤109;1≤mod,w≤109;2≤k≤109)seed,mod,w,k(0\le seed\le 10^9;1\le mod,w\le 10^9;2\le k\le 10^9)，前两个数字代表随机数生成器中的常数，第三个数字代表粘贴操作所需的时间，最后一个数字代表让 Ambition 的电脑死机的最少字符数。

输出格式

对于每组数据，输出一个整数，代表让 Ambition 的电脑死机的最短时间。

样例

输入样例

4
0 1 1 2
8 1 2 79
731 483 166 443
880889741 623864658 89252520 848014988

输出样例

1
14
3185
7402394725