You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Bob 与幸运日

题目信息

时间限制: 1s

空间限制: 256M

输入文件: bob.in

输出文件: bob.out

题目描述

公元 3202 年 1 月 1 日，宇航员 Bob 抵达 Q 星，Q 星有着与地球类似的日历，一年有 $m$ 个月，每个月有 $d$ 天，而 Q 星的每个星期有 $w$ 天，且 $w$ 恰好是个质数。Q 星人认为，在一年中，若第 $x$ 月的第 $y$ 天恰好是星期 $a$，且第 $y$ 月的第 $x$ 天恰好是星期 $b$，那么这两天将构成一对幸运日，我们可以用二元组 $(x, y)$ 来表示这对幸运日。公元 3202 年，Q 星的 1 月 1 日正好是星期一，Bob 计划在 Q 星游玩一年，他想知道在这一年中，一共有多少对幸运日。

注意，$x = y$ 是允许的，在这种情况下 $x$ 月的第 $y$ 天和 $y$ 月的第 $x$ 天是同一天。

输入格式

本题有多组输入。

第一行一个整数 $T$ 表示数据组数。

接下来 $T$ 行，一行五个正整数 $m, d, w, a, b$，意义如题所示。

输出格式

输出一共 $T$ 行，一行一个整数，表示幸运日的对数。

样例

样例输入1

3
4 5 7 2 3
5 4 3 1 1
114514 1919810 65537 824 127

样例输出1

1
6
4

样例解释1

2 月的第 4 天是星期二，4 月的第 2 天是星期三，所以 $(2, 4)$ 是一对幸运日

样例解释2

一共有6组解，$(1, 1), (1, 4), (2, 3), (3, 2), (4, 1), (4, 4)$

数据范围与提示

• 对于测试点1，满足 $k=12, d=30, w=7$
• 对于测试点2-3，满足 $m, d\leq 1000$
• 对于测试点4-6，满足 $w\leq 10^5$
• 对于测试点7-8，满足数据在合法取值范围内随机生成
• 对于测试点9-10，无特殊限制
• 对于所有数据，$T\leq 10, m, d, w\leq 10^9, a, b\in [1, w]$，保证 $w$ 是质数