Virat Kohli and Rohit Sharma are warming up for the World Cup at the Brisbane Cricket Ground, commonly known as "The Gabba". Their coach has asked them to go to the ground at the crack of dawn, and then jog around the stadium in laps. The Cricket Ground has poles spaced equally apart and numbered sequentially from 1 to N. The first M-1 poles lead up to the entrance of the stadium, and the poles numbered M, M+1, ... N are arranged circularly around the stadium, with pole M being next to pole N. Both players start running from pole 1. They always go from pole i to pole i+1, except when i = N, where they go from pole N to pole M.

Due to their different levels of fitness - something that their coach is quite upset about with Virat, that being another story - they have different running speeds P and Q, measured in poles/minute. They have been asked to run for ‘S’ minutes each. Since they can’t keep running for long, the coach has asked them to do short sprints of 1 minute each. First, Virat sprints and covers P poles in 1 minute and stops. Then Rohit sprints and covers Q poles in 1 minute and stops. Virat starts again, and they keep doing this for 2*S minutes (S minutes each). Virat and Rohit are considered to meet if they are at the same pole at the end of some minute. Can you tell how many times they will meet during their jogging routine?

Input:
The first line contains the number of test cases, T. This is followed by T lines, one for each test case. Each test case contains five integers - N, M, S, P and Q.
Output:
For each test case, output the answer on a new line.
Constraints:
1 ≤ T ≤ 100
1 ≤ M < N ≤ 500
1 ≤ S ≤ 100000
1 ≤ P,Q ≤ 500
P ≠ Q
Sample Input:
2
4 1 4 2 3
5 3 10 1 2
Sample Output:
1
3
Explanation:
For the first example, Kohli’s position at the end of his 1st, 2nd, 3rd & 4th minutes of run is {3, 1, 3, 1} respectively. While Rohit’s position at the end of his 1st, 2nd, 3rd & 4th minutes of run is {4, 3, 2, 1} respectively. Therefore, they meet exactly once after 8 minutes (their 4 minutes) at pole 1.
For the second example, they would meet at the end of their 3rd (total 6th), 6th (total 12th) & 9th (total 18th) minute of run.

见题面

见题面