F. Faster Route
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob want to travel from Pui Ching Middle School (PCMS) to La Salle College (LSC).

In this world, PCMS and LSC are located on opposite sides of the same road. PCMS is located at the start of the road, while LSC is located at the end of the road. There are two pedestrian crossings with traffic lights in front of both schools. Both traffic lights just turned from green to red at time 0.

Refer to the following figure for the layout.

It takes 1 unit time to cross the road, and takes $$$C$$$ unit time to walk from the start of the road to the end of the road. The traffic light of the pedestrian crossing in front of PCMS operates in a period of $$$A$$$ unit time. It means that the traffic light would be red for $$$A$$$ unit time, then green for $$$A$$$ unit time, and so on, alternating every $$$A$$$ units.

Formally, you may cross the road if you arrive at the crossing in front of PCMS in time $$$A$$$, $$$A+1$$$, ..., $$$2A-1$$$, $$$3A$$$, $$$3A+1$$$, ..., $$$4A-1$$$, ...

Similarly, the traffic light of the pedestrian crossing in front of LSC operates in a period of $$$B$$$ unit time.

Alice would take the pedestrian crossing in front of PCMS to cross the road first, then travel along the road to LSC, while Bob would travel along the road to LSC first, then take the pedestrian crossing in front of LSC.

Find the number of pairs $$$(u, v)$$$ where $$$0 \leq u \leq U$$$, $$$0 \leq v \leq V$$$ and satisfies the following conditions:

  • Alice starts at time $$$u$$$.
  • Bob starts at time $$$v$$$.
  • The person who starts strictly later, arrives at LSC strictly earlier.
Input

Each input contains multiple test cases. The first line contains the number of test cases $$$T$$$ $$$(1 \leq T \leq 100)$$$. The description of the test cases follows.

The first and only line of each test case contains five integers $$$A$$$, $$$B$$$, $$$C$$$, $$$U$$$, $$$V$$$ ($$$1 \leq A, B \leq 10^5$$$, $$$1 \leq C, U, V \leq 10^9$$$).

It is guaranteed that the sum of $$$A + B$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case, output a single integer on a new line: the number of pairs $$$(u, v)$$$ that satisfy the conditions.

Examples
Input
3
3 2 2 5 5
314 159 265 358 979
2025 20 25 20252025 20262026
Output
2
49141
10221041660
Input
5
5 145 990758033 183587786 177096537
1 1274 114817991 539087542 366293156
529 2 42793654 337687912 536236694
2 465 57138389 522674854 135110507
172 7 829280391 447601408 938200233
Output
6291814931
116390044533
44532871738
15622352866
18970828916
Note

In the first test case of Sample 1, the only two satisfied $$$(u, v)$$$ are $$$(0, 1)$$$ and $$$(3, 2)$$$.

When $$$u=0$$$, $$$v=1$$$:

  • Alice starts at time $$$0$$$.
  • Alice waits until time $$$3$$$ to use the crossing, and arrives at the opposite side at time $$$4$$$.
  • Alice walks down the street and arrives at LSC at time $$$6$$$.
  • Bob starts at time $$$1$$$.
  • Bob walks down the street and arrives at the crossing in front of LSC at time $$$3$$$.
  • Bob immediately uses the crossing, arrives at the LSC at time $$$4$$$.
  • Bob starts strictly later than Alice, but arrives at LSC strictly earlier.

When $$$u=3$$$, $$$v=2$$$:

  • Alice starts at time $$$3$$$.
  • Alice immediately uses the crossing, arrives at the opposite side at time $$$4$$$
  • Alice walks down the street and arrives at LSC at time $$$6$$$.
  • Bob starts at time $$$2$$$.
  • Bob walks down the street and arrives at the crossing in front of LSC at time $$$4$$$.
  • Bob waits until time $$$6$$$ to use the crossing, and arrives at LSC at time $$$7$$$.
  • Alice starts strictly later than Bob, but arrives at LSC strictly earlier.

All other $$$(u, v)$$$ where $$$0 \leq u \leq 5, 0 \leq v \leq 5$$$ do not satisfy the third condition.