说明

机器人宝宝又要听机器人妈妈讲故事了。由于机器人宝宝的记忆力超常，所以机器人妈妈每天讲的故事都要接在上一个故事后面。假设机器人妈妈讲的第一个故事是$X_1$,那么第二个是$X_2$,第$i$个是$X_i= (a * X_{i-1} + b)$% $c$ + 1。现在你希望知道第$n$天机器人妈妈讲的故事是什么。

输入格式

第一行输入一个整数 $T$ 表示有$T$组数据;

接下来每一行输入5个整数$X_1, a , b, c, n$

输出格式

求第$n$天机器人妈妈讲的故事是什么

样例

input1

2
1 1 1 1000 2
394706 314559 674595 559832 4431920000000001

output1

3
554658

数据范围

$1 \leqslant T \leqslant 100$

$1\leqslant X_1 \leqslant 1000000$

$1 \leqslant a \leqslant 1000000$

$1 \leqslant b \leqslant 1000000$

$1 \leqslant c \leqslant 1000000$

$2 \leqslant n \leqslant 1e18$