/ 
実行時間制限: 3 sec / メモリ制限: 1024 MB
配点 : 700 点
問題文
X さんと Y さんの 2 人のプログラマが、競技プログラミングを始めることになりました。
競技プログラミングの実力は、「レベル」と呼ばれる正の整数で表され、はじめ X さんのレベルは A_X、Y さんのレベルは A_Y です。2 人はこれから練習メニューをこなすことで、レベルを上げていきます。
2 人のレベルの上がり方について、次のことが分かっています：
- X さんはちょうど B_X 個の練習メニューをこなすたびに、レベルがひとつ上がります。
- Y さんはちょうど B_Y 個の練習メニューをこなすたびに、レベルがひとつ上がります。
n = 1, 2, \ldots, N のうちで次を満たすものはいくつあるかを答えてください。
- 2 人がちょうど n 個ずつの練習メニューをこなした場合、2 人の最終的なレベルは等しくなる。
一つの入力ファイルにつき、T 個のテストケースに答えてください。
制約
- 1\leq T\leq 2\times 10^5
- 1\leq N\leq 10^{9}
- 1\leq A_X, B_X, A_Y, B_Y \leq 10^6
入力
入力は以下の形式で標準入力から与えられます。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられます。
N A_X B_X A_Y B_Y
出力
答えを出力してください。
入力例 1
5 10 5 3 4 2 5 5 3 4 2 100 5 3 4 2 10 5 3 4 3 10 5 10 5 9
出力例 1
6 3 6 0 9
ひとつめのテストケースについて説明します。
n = 1, 2, \ldots, 10 に対して、n 個の練習メニューをこなした場合の 2 人のレベルは次のようになります：
- X さんのレベル：5, 5, 6, 6, 6, 7, 7, 7, 8, 8
- Y さんのレベル：4, 5, 5, 6, 6, 7, 7, 8, 8, 9
6 個の n （n = 2, 4, 5, 6, 7, 9）の場合に 2 人のレベルが等しくなります。したがって答えは 6 となります。
Score : 700 points
Problem Statement
Two programmers, X and Y, are going to start competitive programming.
One's skill in competitive programming is represented by a positive integer called the level. Initially, X's level is A_X, and Y's level is A_Y. The two will do learning tasks to raise their levels.
We know that they level up as follows.
- X's level raises by one after every B_X learning tasks.
- Y's level raises by one after every B_Y learning tasks.
How many among n = 1, 2, \ldots, N satisfy the following?
- X's level and Y's level are equal when each of them has done exactly n learning tasks.
Process T test cases per input file.
Constraints
- 1\leq T\leq 2\times 10^5
- 1\leq N\leq 10^{9}
- 1\leq A_X, B_X, A_Y, B_Y \leq 10^6
Input
Input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each case is in the following format:
N A_X B_X A_Y B_Y
Output
Print the answers.
Sample Input 1
5 10 5 3 4 2 5 5 3 4 2 100 5 3 4 2 10 5 3 4 3 10 5 10 5 9
Sample Output 1
6 3 6 0 9
We will describe the first test case.
For each n = 1, 2, \ldots, 10, the two's levels after doing n learning tasks are as follows.
- X's level: 5, 5, 6, 6, 6, 7, 7, 7, 8, 8.
- Y's level: 4, 5, 5, 6, 6, 7, 7, 8, 8, 9.
There are six scenarios (n = 2, 4, 5, 6, 7, 9) where the two's levels are equal, so the answer is 6.