Ash is on his way to becoming the Pokemon Master. His pokemon can perform the following moves:  
- Tackle - Deal damage worth $X$ points  
- Grow - Increase damage by $Y$ points i.e. $X$ = $X$ + $Y$ 
But, it can only perform Grow first (0 or more times) and then tackle (0 or more) times after which it cannot perform Grow again.

That is, it cannot perform the Grow operation once it has performed the tackle operation.  
A pokemon can be caught only if it’s health is exactly 1. A wild pokemon has appeared and has health worth $H$ points. Find the minimum number of moves required to catch it or say that it is not possible.  

-----Input:-----
- 
The first line of the input consists of a single integer $T$ denoting the number of test cases.
- 
Each test case consists of 3 space-separated integers $H$, $X$ and $Y$.

-----Output:-----
- For each test case, print a single line containing one integer - the minimum number of moves required to catch the pokemon if it is possible to catch it else print -1.

-----Constraints-----
- 
1 <= $T$ <= 103
- 
1 <=  $X$, $Y$ < $H$ <= 109

-----Subtasks-----
Subtask #1 (30 points):
- 1 <=  $X$, $Y$ < $H$ <= 1000
Subtask #2 (70 points):
- Original Constraints

-----Sample Input:-----
2

101 10 10

11 3 3  

-----Sample Output:-----
6

-1  

-----EXPLANATION:-----
- 
Example Case 1:

Ash can make use of Grow once. So $X$ = 10 + 10 = 20

Then he can do Tackle 5 times to decrease $H$ to 1.

OR

Ash can make use of Grow 4 times. So $X$ = 10 + 4*10 = 50

Then he can do Tackle 2 times to decrease $H$ to 1.

Hence, a total of 6 moves are required either way which is minimum.  
- 
Example Case 2:

No matter how many times Ash uses Grow or Tackle, pokemon can never be caught.

Difficulty: interview

Starter code:

Solutions:
def Testcase():
    h,x,y = [int(x) for x in input().strip().split()]
    
    h = h-1
    yt = h//y +1
    # print(yt)
    flag=0
    ans = 100000000009
 
    for i in range(0,yt):
        temp = x+i*y
        if h%temp==0:
            flag = 1
            cl =i+int(h/temp)
            # print(temp,cl)
            ans = min(ans,cl)
            # print(temp,ans,i)
    print(ans if flag==1 else '-1')
    
    
t = int(input())
while t>0:
    Testcase()
    
    t-=1

# cook your dish here

t = int(input())
for rep in range(t):
    h,x,y = list(map(int,input().split()))
    req = h - 1
    mini = 1000000000
    g = 0
    t = 0
    base = x
    f = 0
    while base <= req:
        if req % base == 0:
            f = 1
            t = req // base
            if g + t < mini:
                mini = g + t
        base = base + y
        g = g + 1
    if f == 1:
        print(mini)
    else:
        print(-1)


# cook your dish here
try:
    from functools import reduce

    def factors(n):    
        return set(reduce(list.__add__, 
                    ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))
    b = ()
    test = int(input())
    for i in range (test):
        flag = 0
        move = []
        h , x , y = list(map(int,input().split(' ')))
        b = factors(h-1)
        h -= 1
        if(h == x):
            print("0")
        else:
            for j in b:
                if(j >= x):
                    if(j==x ):
                        flag = 1 
                        move.append(h//j)
                    elif((j-x)%y == 0 ):
                        flag = 1
                        move.append(((j-x)//y + h/j ))
                    
                    
            if(flag == 0):
                print("-1")
            else:
                print(int(min(move)%((10**9)+7)))
                
                
except EOFError:
	pass

# cook your dish here
try:
    from functools import reduce

    def factors(n):    
        return set(reduce(list.__add__, 
                    ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))
    b = ()
    test = int(input())
    for i in range (test):
        flag = 0
        move = []
        h , x , y = list(map(int,input().split(' ')))
        b = factors(h-1)
        h -= 1
        if(h == x):
            print("0")
        else:
            for j in b:
                if(j >= x):
                    if(j==x ):
                        flag = 1 
                        move.append(h//j)
                    elif((j-x)%y == 0 ):
                        flag = 1
                        move.append(((j-x)//y + h/j ))
                    
                    
            if(flag == 0):
                print("-1")
            else:
                print(int(min(move)%((10**9)+7)))
                
                
except EOFError:
	pass

# cook your dish here
try:
    from functools import reduce

    def factors(n):    
        return set(reduce(list.__add__, 
                    ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))
    b = ()
    test = int(input())
    for i in range (test):
        flag = 0
        move = []
        h , x , y = list(map(int,input().split(' ')))
        b = factors(h-1)
        h -= 1
        if(h == x):
            print("0")
        else:
            for j in b:
                if(j >= x):
                    if(j==x ):
                        flag = 1 
                        move.append(h//j)
                    elif((j-x)%y == 0 ):
                        flag = 1
                        move.append(((j-x)//y + h/j ))
                    
                    
            if(flag == 0):
                print("-1")
            else:
                print(int(min(move)%((10**9)+7)))
                
                
except EOFError:
	pass

# cook your dish here
try:
    from functools import reduce

    def factors(n):    
        return set(reduce(list.__add__, 
                    ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))
    b = ()
    test = int(input())
    for i in range (test):
        flag = 0
        move = 1000
        h , x , y = list(map(int,input().split(' ')))
        b = factors(h-1)
        h -= 1
        if(h == x):
            print("0")
            move = 999
        else:
            for j in b:
                if(j >= x):
                    if(j==x ):
                        flag = 1 
                        if(move > h//j):
                            move = h//j
                    elif((j-x)%y == 0 ):
                        flag = 1
                        if(move > ((j-x)//y + h/j )):
                            move = ((j-x)//y + h/j )
                    
                    
            if(flag == 0):
                print("-1")
            else:
                print(int(move%((10**9)+7)))
                
                
except EOFError:
	pass

# cook your dish here
try:
    from functools import reduce

    def factors(n):    
        return set(reduce(list.__add__, 
                    ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))
    b = ()
    test = int(input())
    for i in range (test):
        flag = 0
        move = 1000
        h , x , y = list(map(int,input().split(' ')))
        b = factors(h-1)
        h -= 1
        if(h == x):
            print("0")
            move = 999
        else:
            for j in b:
                if(j >= x):
                    if(j==x ):
                        flag = 1 
                        if(move > h//j):
                            move = h//j
                    elif((j-x)%y == 0 ):
                        flag = 1
                        if(move > ((j-x)//y + h/j )):
                            move = ((j-x)//y + h/j )
                    
                    
            if(flag == 0):
                print("-1")
            else:
                print(int(move)%((10**9)+7))
                
                
except EOFError:
	pass

# cook your dish here
try:
    from functools import reduce

    def factors(n):    
        return set(reduce(list.__add__, 
                    ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))
    b = ()
    test = int(input())
    for i in range (test):
        flag = 0
        move = 1000
        h , x , y = list(map(int,input().split(' ')))
        b = factors(h-1)
        h -= 1
        if(h == x):
            print("0")
            move = 999
        else:
            for j in b:
                if(j >= x):
                    if(j==x ):
                        flag = 1 
                        if(move > h//j):
                            move = h//j
                    elif((j-x)%y == 0 ):
                        flag = 1
                        if(move > ((j-x)//y + h/j )):
                            move = ((j-x)//y + h/j )
                    
                    
            if(flag == 0):
                print("-1")
            else:
                print(int(move))
                
                
except EOFError:
	pass

# cook your dish here

t = int(input())
for rep in range(t):
    h,x,y = list(map(int,input().split()))
    req = h - 1
    mini = 1000000000
    g = 0
    t = 0
    base = x
    f = 0
    while base <= req:
        if req % base == 0:
            f = 1
            t = req // base
            if g + t < mini:
                mini = g + t
        base = base + y
        g = g + 1
    if f == 1:
        print(mini)
    else:
        print(-1)


from sys import stdin
from functools import reduce

def factors(n):    
    return list(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))

for _ in range(int(stdin.readline())):
    h, x, y = list(map(int, stdin.readline().split()))
    arr = factors(h-1)
    ans = 1000000001
    cond = False
    for i in range(len(arr)):
        if arr[i]>=x:
            m = arr[i]-x
            if m%y == 0:
                cond = True
                ans = min(ans, m//y + (h-1)//arr[i])
    if cond == True:
        print(ans)
    else:
        print(-1)
            
            


# cook your dish here
import math  
 
def printDivisors(n,X,l) : 
    list = []   
    for i in range(1, int(math.sqrt(n) + 1)) : 
        if (n % i == 0) : 
            if (n / i == i) : 
                list.append(i)
                a=0
            else :  
                list.append(i)
                list.append(int(n / i)) 
                       
    for i in list[::-1] :
        if(i-X>=0):
            l.append(i)
          

T=int(input())
for _ in range(T):
    H,X,Y=list(map(int,input().split()))
    l=[]
    printDivisors(H-1,X,l)
    mv=2*H
    for i in l:
        a=(i-X)//Y
        if(a*Y==(i-X)):
            v=((H-1)//i)+a
            if(v<mv):
                mv=v

    if(mv>H):
        print(-1)

    else:
        print(mv)
        


from math import sqrt

INF = float('inf')

def divs(n):
    d = []

    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            d.append(i)

            if n // i != i:
                d.append(n // i)

    return d

for _ in range(int(input())):
    h, x, y = map(int, input().split())
    h -= 1

    d = divs(h)

    mini = INF

    for i in d:
        if i - x >= 0 and (i - x) % y == 0:
            f = (i - x) // y + h // i

            mini = min(mini, f)

    if mini == INF:
        print(-1)
    else:
        print(mini)