John and Brus believe that number \textbf{N} is a very bad number. Thus they try to avoid it every time and everywhere. Now the guys would like to represent number \textbf{M} as a sum of positive numbers, each of which not exceeding \textbf{K}. But don’t forget about the bad number \textbf{N!} Each summand must not be divisible by \textbf{N}, moreover the number of summands also must not be divisible by \textbf{N}. Your task is to find the minimal possible number of summands in such representation of \textbf{M}. For example, if \textbf{N=3}, \textbf{M=11}, \textbf{K=6} then we can represent \textbf{M} as \textbf{5+6}, but as far as \textbf{6} is divisible by \textbf{3} we must have at least \textbf{3} summands. But as far as \textbf{N=3} we can’t have 3 summands and thus the answer is \textbf{4}. One of the possible ways to represent \textbf{M} is \textbf{11=4+4+2+1}. \InputFile The first line contains single integer \textbf{T} -- the number of test cases. Each test case consists of a single line containing three integers \textbf{N}, \textbf{M} and \textbf{K} separated by single spaces. \OutputFile For each test case print a single line containing the minimal possible number of summands according to the requirements described above. If it is impossible to do this output \textbf{"-1"} (quotes for clarity) instead. \textbf{Constraints} \textbf{1} <= \textbf{T} <= \textbf{74}, \textbf{1} <= \textbf{N}, \textbf{M}, \textbf{K} <= \textbf{1000000000} (\textbf{10^9}).