[SDOI2013]随机数生成器

题目描述

小W喜欢读书,尤其喜欢读《约翰克里斯朵夫》。最近小W准备读一本新书,这本书一共有$P$页,页码范围为$0 \cdots P-1$。 小W很忙,所以每天只能读一页书。为了使事情有趣一些,他打算使用NOI2012上学习的线性同余法生成一个序列,来决定每天具体读哪一页。 我们用Xi来表示通过这种方法生成出来的第$i$个数,也即小$W$第$i$天会读哪一页。这个方法需要设置$3$个参数$a,b,X1$,满足$0\leq a,b,X1\leq p-1$,且$a,b,X1$都是整数。按照下面的公式生成出来一系列的整数:$X_{i+1} \equiv aX_i+b \pmod p$其中$mod$表示取余操作。 但是这种方法可能导致某两天读的页码一样。 小W要读这本书的第$t$页,所以他想知道最早在哪一天能读到第t页,或者指出他永远不会读到第$t$页。

输入输出格式

输入格式


输入含有多组数据,第一行一个正整数$T$,表示这个测试点内的数据组数。 接下来T行,每行有五个整数$p$,$a$,$b$,$X1$,$t$,表示一组数据。保证$X1$和$t$都是合法的页码。 注意:$P$一定为质数

输出格式


共$T$行,每行一个整数表示他最早读到第$t$页是哪一天。如果他永远不会读到第$t$页,输出$-1$。

输入输出样例

输入样例 #1

3
7  1 1 3 3
7  2 2 2 0
7  2 2 2 1

输出样例 #1

1 
3 
-1

说明

$0\leq a\leq P-1,0\leq b\leq P-1,2\leq P\leq 10^9$