# Balls Rearrangement

Time Limit: 9000/3000 MS (Java/Others)

Memory Limit: 65535/32768 K (Java/Others)

## Description

Bob has N balls and A boxes. He numbers the balls from 0 to N-1, and numbers the boxes from 0 to A-1. To find the balls easily, he puts the ball numbered x into the box numbered a if x = a mod A.   Some day Bob buys B new boxes, and he wants to rearrange the balls from the old boxes to the new boxes. The new boxes are numbered from 0 to B-1. After the rearrangement, the ball numbered x should be in the box number b if x = b mod B.
This work may be very boring, so he wants to know the cost before the rearrangement. If he moves a ball from the old box numbered a to the new box numbered b, the cost he considered would be |a-b|. The total cost is the sum of the cost to move every ball, and it is what Bob is interested in now.

## Input

The first line of the input is an integer T, the number of test cases.(0<T<=50)
Then T test case followed. The only line of each test case are three integers N, A and B.(1<=N<=1000000000, 1<=A,B<=100000).

## Output

For each test case, output the total cost.

## Sample Input

3
1000000000 1 1
8 2 4
11 5 3

## Sample Output

0
8
16

zhuyuanchen520

## Source

2013 Multi-University Training Contest 2