寻宝

题号：NC16605
时间限制：C/C++/Rust/Pascal 10秒，其他语言20秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

由依是战线佯攻部队的辅助人员,在岩泽消失之后,企图代替岩泽成为GDM主唱。但是SSS战线的领袖仲村由理是不会轻易让她加入的,于是由理子给了由依一项艰巨的任务：去一个地下迷宫寻找宝石!
这个迷宫由n个房间组成,编号为0到n - 1,每个房间里都有一颗宝石,房间通过单向通道连接。每个房间里有两个门：一个通向第R个房间(R=(a·v²+ b·v + c) mod n),另一个通向迷宫出口,一旦离开迷宫,便会触发自毁机关,将再也没有机会继续收集宝石。现在,她可以在任何地点进入迷宫，沿隧道移动并收集宝石。

由依想尽可能地收集宝石,你能算出她能从迷宫中获得的最大宝石数量是多少吗？

ps:(a·v²+ b·v + c) mod n表示第v个门通向第(a·v²+b·v+c)%n个门

输入描述:

输入的第一行包含一个整数T，表示测试组数。
每个测试用例前面都有一个空白行。
每个测试用例包含四个整数a，b，c和n。

输出描述:

对于每个测试用例输出一个数表示她可以从迷宫中获取的最大宝石数量。

示例1

输入

复制

3

1  2  0  64

0  2  1  47

0  3  5  128

输出

复制

5
23
64

说明

起点很重要。例如，假设在第一个例子中，由依从 0号房间 开始测试。她的两个选择是通向房间0的通道和通往迷宫外的通道 。更好的策略是从2号房间开始并沿着路径 2 → 8 → 16 → 32 → 0 → 出口。

备注:

T<=10，保证满足n>300的最多两组
n≤2²⁴