the-array-walk-8

There is an infinite one dimensional array ranging from (-infinity, infinity). You are currently at cell number 0. Your goal is to reach cell number H. There are two kinds of moves allowed.
 Make U steps to the right (positive side).
 Make D steps to the left (negative side).

Your task is to find the minimum number of moves to reach your goal.

Input & Output:

The first line contains the number of test cases T. Each of the next T lines contains 3 space separated integers, H U D. For each test case, output one line with an integer, the minimum number of moves required to reach H from 0. If it is impossible , print -1 instead.

Constraints:
T ≤ 10000
1 ≤ H, U, D ≤ 10^9

SAMPLE INPUT
2
3 2 1
3 2 2

SAMPLE OUTPUT
3
-1

Explanation

1) In the first sample case, first move 2 steps to the right to reach cell number 2. Then 1 step to the left to reach cell number 1 and finally 2 more steps to the right to reach the goal. Thus 3 moves are required which is the minimum.

2) Because both U and D are even, you will always be in an even cell. Thus there is no way to reach cell number 3.

Source: hackerearth | Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics


Solutions: