#102488. [BZOJ 2488] Pku3902 The Bad Number

John and Brus believe that number is a very bad number．Thus they try to avoid it every time and everywhere．
Now the guys would like to represent number as a sum of positive numbers，each of which not exceeding ．But don’t forget about the bad number ！Each summand must not be divisible by ，moreover the number of summands also must not be divisible by ．
Your task is to find the minimal possible number of summands in such representation of ．
For example，if then we can represent as ，but as far as is divisible by we must have at least summands．But as far as we can’t have summands and thus the answer is ．One of the possible ways to represent is ．

给你三个整数 ，求一个最小的 ，使得 能够被分成 个正整数的和。
并且这些整数要满足：（一）不能是 的倍数，（二）大小不能超过 ，并且 也不能是 的倍数。

The first line contains single integer – the number of test cases．Each test case consists of a single line containing three integers and separated by single spaces．

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 -1 （quotes for clarity） instead．

样例输入 #1

2
3 11 6
2 12 47

样例输出 #1

4
-1

的数据满足：。