配点 : 4 点
問題文
满足以下条件的一组整数 查找 x,y 的编号。
- 0 \leq x, y \leq N
- Ax+By 是 它仅由 C 的倍数 您将获得
T 测试用例,因此请找到每个测试用例的答案。
制約
3 点的部分点数据满足以下条件。
- T = 1
- 1 \leq N \leq 1000
- 1 \leq A,B,C \leq 10^9
满分数据满足以下条件,除上述条件外, 将授予 1 积分。 (满分解法非常困难,建议您跳过一次。)
- 1 \leq T \leq 10^5
- 1 \leq N \leq 10^9
- 1 \leq A,B,C \leq 10^9
入力
输入是按以下格式从标准输入给出的。
T case_1 \vdots case_T
每个测试用例均按以下格式给出。 请输出
N A B C
出力
T 行。 请打印 i 行中,case_i 的答案。
入力例 1
1 2 3 4 5
出力例 1
2
入力例 2
1 1000 314159265 271828182 2023
出力例 2
496