Alice mixed up the words transmutation and permutation! She has an array (a) specified via three integers (n), (b), (c): the array (a) has length (n) and is given via (a_i = b\cdot (i - 1) + c) for (1\le i\le n). For example, if (n=3), (b=2), and (c=1), then (a=2 \cdot 0 + 1, 2 \cdot 1 + 1, 2 \cdot 2 + 1 = 1, 3, 5). Now, Alice really enjoys permutations of (0, \ldots, n-1)(^{\text{∗}}) and would like to transform (a) into a permutation. In one operation, Alice replaces the maximum element of (a) with the (\operatorname{MEX})(^{\text{†}}) of (a). If there are multiple maximum elements in (a), Alice chooses the leftmost one to replace. Can you help Alice figure out how many operations she has to do for (a) to become a permutation for the first time? If it is impossible, you should report it. (^{\text{∗}})A permutation of length (n) is an array consisting of (n) distinct integers from (0) to (n-1) in arbitrary order. Please note, this is slightly different from the usual definition of a permutation. For example, (1,2,0,4,3) is a permutation, but (0,1,1) is not a permutation ((1) appears twice in the array), and (0,2,3) is also not a permutation ((n=3) but there is (3) in the array). (^{\text{†}})The (\operatorname{MEX}) of an array is the smallest non-negative integer that does not belong to the array. For example, the (\operatorname{MEX}) of (0, 3, 1, 3) is (2) and the (\operatorname{MEX}) of (5) is (0). Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^5)). The description of the test cases follows. The only line of each test case contains three integers (n), (b), (c) ((1\le n\le 10^{18}); (0\le b), (c\le 10^{18})) — the parameters of the array. For each test case, if the array can never become