小 $W$ 喜欢读书，尤其喜欢读《约翰克里斯朵夫》。
最近小 $W$ 准备读一本新书，这本书一共有 $p$ 页，页码范围为 $0..p-1$。
小 $W$ 很忙，所以每天只能读一页书。
为了使事情有趣一些，他打算使用 NOI2012 上学习的线性同余法生成一个序列，来决定每天具体读哪一页。
我们用 $X_i$ 来表示通过这种方法生成出来的第 $i$ 个数，也即小 $W$ 第 $i$ 天会读哪一页。
这个方法需要设置 $3$ 个参数 $a,b,X_1$，满足 $0 \le a,b,X_1 \le p-1$，且 $a,b,X_1$ 都是整数。
按照下面的公式生成出来一系列的整数。
$$X_{i+1}=(aX_i+b) \bmod p$$
其中 $\bmod p$ 表示前面的数除以 $p$ 的余数。
可以发现，这个序列中下一个数总是由上一个数生成的，而且每一项都在 $0..p-1$ 这个范围内，是一个合法的页码。
同时需要注意，这种方法有可能导致某两天读的页码完全一样。
小 $W$ 非常急切的想去读这本书的第 $t$ 页。
所以他想知道，对于一组给定的 $a,b,X_1$，如果使用线性同余法来生成每一天读的页码，最早读到第 $t$ 页是在哪一天，或者指出他永远不会读到第 $t$ 页。
输入含有多组数据，第一行一个正整数 $T$，表示这个测试点内的数据组数。
接下来 $T$ 行，每行有五个整数 $p，a，b，X_1，t$，表示一组数据。保证 $X_1$ 和 $t$ 都是合法的页码。
注意：$P$ 一定为质数。
共 $T$ 行，每行一个整数表示他最早读到第 $t$ 页是哪一天。
如果他永远不会读到第 $t$ 页，输出 $-1$。
$0 \le a \le p-1$,
$0 \le b \le p-1$,
$2 \le p \le 10^9$
3
7 1 1 3 3
7 2 2 2 0
7 2 2 2 1