F. 机惨

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

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

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

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

不幸的是，Ambition 走前，为了防止 nkxjlym 机惨他，在电脑里写了一段程序，使得 nkxjlym 进行操作1的时间不是一个固定值，而是 $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\le t\le 10^4)$，代表数据组数。

对于每组数据，输入仅有一行四个整数 $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