爱丽丝混淆了嬗变和排列这两个词!她有一个通过三个整数 $$$n$$$、$$$b$$$、$$$c$$$ 指定的数组 $$$a$$$:数组 $$$a$$$ 的长度为 $$$n$$$,并通过 $$$a_i = b\cdot (i - 1) + c$$$ for $$$1\le i\le n$$$ 给出。例如,如果 $$$n=3$$$、$$$b=2$$$ 和 $$$c=1$$$,则 $$$a=[2 \cdot 0 + 1, 2 \cdot 1 + 1, 2 \cdot 2 + 1] = [1, 3, 5]$$$。
现在,Alice 非常喜欢 $$$[0, \ldots, n-1]$$$$$$^{\text{*}}$$$ 的排列,并且希望将 $$$a$$$ 转换为排列。在一次操作中,Alice 将 $$$a$$$ 的最大元素替换为 $$$a$$$ 的 $$$\operatorname{MEX}$$$$$$^{\text{†}}$$$。如果 $$$a$$$ 中有多个最大元素,Alice 会选择最左边的一个进行替换。
你能帮助 Alice 算出她需要进行多少次操作才能使 $$$a$$$ 第一次成为排列吗?如果不可能,您应该报告。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。
每个测试用例的唯一行包含三个整数 $$$n$$$、$$$b$$$、$$$c$$$ ($$$1\le n\le 10^{18}$$$; $$$0\le b$$$、$$$c\le 10^{18}$$$) — 数组的参数。
输出
对于每个测试用例,如果数组永远不能成为排列,则输出 $$$-1$$$。否则,输出使数组成为排列的最少操作次数。
示例
输入 #1
7 10 1 0 1 2 3 100 2 1 3 0 1 3 0 0 1000000000000000000 0 0 1000000000000000000 1000000000000000000 1000000000000000000
输出 #1
0 1 50 2 -1 -1 1000000000000000000
注意
在第一个测试用例中,数组已经是 $$$[0, 1, \ldots, 9]$$$,因此不需要任何操作。
在第三个测试用例中,起始数组是 $$$[1, 3, 5, \ldots, 199]$$$。第一次操作后,$$$199$$$ 被转换为 $$$0$$$。在第二个操作中,$$$197$$$ 被转换为 $$$2$$$。如果继续这样,将需要 $$$50$$$ 操作来获取数组 $$$[0, 1, 2, 3, \ldots, 99]$$$。
在第四个测试用例中,需要两个操作:$$$[1,1,1] \to [0,1,1] \to [0,2,1]$$$。
在第五个测试用例中,过程是 $$$[0,0,0] \to [1,0,0] \to [2,0,0] \to [1,0,0] \to [2,0,0]$$$。这个过程永远重复,所以数组永远不是排列,答案是$$$-1$$$。