该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

$\mathrm{Night}$ 有一天做到了 [NOIP2013]转圈游戏 这个题，感觉这个题实在是太简单了，显示不出难度，所以 $\mathrm{Night}$ 决定把这个题变得难一丢丢来给大家做。

原题面是这样的：

$n$ 个小伙伴（编号从 $0$ 到 $n-1$）围坐一圈玩游戏。按照顺时针方向给 $n$ 个位置编号，从 $0$ 到 $n-1$。最初，第 $0$ 号小伙伴在第 $0$ 号位置，第 $1$ 号小伙伴在第 1 号位置，……，依此类推。

游戏规则如下：每一轮第 $0$ 号位置上的小伙伴顺时针走到第 $m$ 号位置，第 $1$ 号位置小伙伴走到第 $m+1$ 号位置，……，依此类推，第 $n−m$ 号位置上的小伙伴走到第 $0$ 号位置，第 $n-m+1$ 号位置上的小伙伴走到第 $1$ 号位置，……，第 $n-1$ 号位置上的小伙伴顺时针走到第 $m-1$ 号位置。

现在，一共进行了 $10^k$ 轮，请问 $x$ 号小伙伴最后走到了第几号位置。

然后 $\mathrm{Night}$ 把它改了一波参数，让这个游戏不只是会进行 $10^k$ 轮了，而是会进行 $p^k$ 轮。

并且 $\mathrm{Night}$ 还加大了数据范围，改成了多组询问，具体请看输入格式以及数据范围。

Input Format

第一行为一个正整数 $q$ 表示询问次数。

第 $2$ 行到第 $q+1$ 行每行五个整数分别为 $n,m,k,x,p$ 表示一组询问，含义如题目描述所示，每两个整数之间用一个空格隔开。

Output Format

输出 $q$ 行，第 $i$ 行表示第 $i$ 组询问的答案。

Sample

输入样例：

1
10 3 4 5 10

输出样例：

5

Hint

（别想了这个题没有部分分）

请注意常数因子对程序运行时间的影响（就是说你常数不优秀是会爆零的）

对于 $100\%$ 的数据，$1\leq q \leq 10000$，$1 < n \leq 10^{18}$，$0 < m < n$，$1 \leq x \leq n$，$0 < k < 10^{18}$，$1 \leq p \leq 10^{18}$。