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.