Ross, being divorced for three times(yeah, and he is just 30!) had nothing to do so Chandler told him to paint his apartment. Consider the wall is made with labelled bricks 1, 2, 3,.... and so on. Now after choosing Red paint for Ross and Blue for Chandler, they started painting a wall, Ross said he will paint every Xth brick Red, i.e., for some X, he will paint X, 2X, 3X,... etc Red. Similarly Chandler said that he will paint every Yth brick Blue. For some Y, he will paint Y,2Y,3Y,...

After painting the wall they found that some of bricks were painted both Red and Blue. Now they are wondering How many bricks from Brick number A to Brick number B are colored with both colors.

Now it's you to help them telling the number of bricks painted with both colors.

Input

  First line T, number of test case then T lines, one test case per line.

  Each test case, Four integers space separated integers X,Y,A,B.

Output

  For each test case, print the described output in newline.

Constraints

 1 <= T <= 50

 1 <= X, Y <= 1000

 1<= A <= B <= 2·(10^9)