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.

题目描述

小 X 家门前有两个红绿灯，小 X 做完了数学作业，闲着无聊便在窗边观察。他发现这两个红绿灯亮红灯和亮绿灯的时间是相等的，第一个红绿灯亮 $p$ 秒绿灯，再亮 $p$ 秒红灯……，第二个红绿灯亮 $q$ 秒绿灯，再亮 $q$ 秒红灯……，如此循环往复。

现在恰好两个红绿灯都从红灯变成了绿灯，小 X 想要知道未来的 $2\times p\times q$ 秒内，有多少秒满足两个红绿灯都亮绿灯。

输入格式

第一行 $2$ 个正整数 $p,q$，含义见题面。

输出格式

输出一行一个整数表示在未来的 $2\times p\times q$ 秒内，有多少秒满足两个红绿灯都亮绿灯。

2 3

3

18 66

612

2 255

128

提示

样例解释 1

在未来的 $12$ 秒内，第一个红绿灯在第 $1,2,5,6,9,10$ 秒亮绿灯。

第一个红绿灯在第 $1,2,3,7,8,9$ 秒亮绿灯。

在第 $1,2,9$ 秒时，同时亮绿灯，一共 $3$ 秒。

数据范围

本题共有 $12$ 个测试点，每个测试点 $10$ 分。

对于测试点 $1\sim 3$：$1\leq p,q\leq 1000$

对于测试点 $4\sim 5$：$p=1,1\leq q\leq 10^9$

对于测试点 $6\sim 9$：$1\leq p,q\leq 10^9$ 且 $p,q$ 互质，即 $p,q$ 的最大公约数是 $1$

对于测试点 $10\sim 12$：$1\leq p,q\leq 10^9$