题目背景

由于awa公开了$smr2$（summer training round 2） 中waauto的T4代码，这使得waauto非常恼怒

waauto准备执行追杀awa的计划，但是不幸的，有人提前告知了awa，于是他现在在WA城逃窜，但残忍的waauto并不会因此放过他，他准备在awa将要到达的地点等待，以便抓走awa.

抓走干嘛暂且不说（

以下为公开处刑awa

以上为公开处刑awa

题目描述

在WA城有$p$个分地点，组成一个环，编号为0~p-1,规定0->p-1->0是正方向

一开始awa 在编号为$a_1$的节点，每天都会向前移动$k*a_i+g$ 个地点

比如$k=2，g=3，p=10007$,在4城的时候

第二天就会到达4+4*2+3=15城，

p=13，其他情况相同时，第二天会到达2城市

现在waauto想知道，在第n天awa会到达哪里

因为awa的逃窜初值不一定，所以多组数据询问

输入格式

第一行一个T表示数据询问个数

第二行至T+1行，每行五个数，$p,a_1,k,g,n$，意义如题目描述

输出格式

T行，每行一个数，表示第n天，所到达城市的编号

样例

样例输出

1
10007 4 2 3 2

样例输出

15

提示与说明

for 30 pts : $p\le 199,n<p$

for 60 pts: $p\le60000049,n<p$

for 90 pts: $p\le 10^9+7,n<10^{18}$

for all pts:

$0\le a_1,k,g<p\le 2*10^9,n<10^{1000000}$

p是质数

$1\le T \le 10$