T và H là 1 đôi bạn chơi rất thân cùng nhau vào tuyển quốc gia. Thay vì tập trung vào đội tuyển, 2 bạn lại duo rank game rác LQ "thắng bại tại nạp tiền". Sau khi tạch giải quốc gia, nhận ra LQ quá trash, H đã nghe theo tiếng gọi của đấu trường công lý như đàn anh đz, ngầu lòi của mình.
Ngoài tài năng làm nền cho highlight của đối thủ trong mỗi game đấu, T còn có những bài toán giúp làm giảm đi trí thông minh của người chơi. Sau 6996 lần thua H, hôm nay T đã chuẩn bị n viên sỏi để thách đấu với H, bài toán là tìm số cách bỏ ra m viên để còn lại đúng c phần. Trong khi T lọ mọ ngồi đếm, H chưa đến 1s đã có thể tìm ra. Các bạn hãy cùng thử giải bài toán này nhé.
Dòng đầu tiên ở mỗi file input chứa T - số bộ test. Mỗi bộ test có format như sau:
1 dòng duy nhất chứa 3 số nguyên N, M, C.
1 dòng duy nhất chứa kết quả bài toán
1 ≤ T ≤ 100000.
1 ≤ M ≤ N, 0 ≤ C ≤ N - M.
20% số test ứng với N ≤ 15
30% số test ứng với N ≤ 30, T ≤ 100
20% số test ứng với N ≤ 1000
30% số test ứng với N ≤ 100000
Giải thích test 1: {2, 4}
Giải thích test 2: {2}
Giải thích test 3: {2, 3, 4}, {1, 3, 4}, {1, 2, 4}, {1, 2, 3}
## Input
Dòng đầu tiên ở mỗi file input chứa T - số bộ test. Mỗi bộ test có format như sau:1 dòng duy nhất chứa 3 số nguyên N, M, C.
## Output
1 dòng duy nhất chứa kết quả bài toán
[samples]
## Scoring
1 ≤ T ≤ 100000.1 ≤ M ≤ N, 0 ≤ C ≤ N - M.20% số test ứng với N ≤ 1530% số test ứng với N ≤ 30, T ≤ 10020% số test ứng với N ≤ 100030% số test ứng với N ≤ 100000
## Note
Giải thích test 1: {2, 4}Giải thích test 2: {2}Giải thích test 3: {2, 3, 4}, {1, 3, 4}, {1, 2, 4}, {1, 2, 3}
**Definitions**
Let $ N \in \mathbb{Z} $ be the number of non-starting properties, arranged in a circle indexed $ 2, 3, \dots, N+1 $, with position $ 1 $ as the fixed starting position (government-owned).
Let $ V_s, V_b, V_l \in \mathbb{Z} $ be the fixed dice values for Seo, B21, and Lowie, respectively.
Players move in cyclic order: Seo, B21, Lowie, repeating.
Each player starts at position $ 1 $.
After $ k $ total dice rolls, the position of player $ p $ is computed modulo $ N $, offset appropriately.
**Constraints**
- $ 3 \leq N \leq 10^5 $
- $ 1 \leq V_s, V_b, V_l \leq N $
- Each player makes up to $ 10^9 $ moves (total $ 3 \times 10^9 $ rolls maximum).
**Objective**
Find the smallest $ t \in \{1, 2, \dots, 3 \times 10^9\} $ such that after the $ t $-th roll, the current player lands on a property owned by another player.
If no such $ t $ exists within $ 3 \times 10^9 $ rolls, output $ 3000000000 $.
Let $ r = \lceil t / 3 \rceil $ be the number of full rounds completed before roll $ t $.
Define the position of each player after $ m $ moves:
- Seo’s position after $ m $ moves: $ 1 + m \cdot V_s \mod N $, adjusted to $ \{2, \dots, N+1\} $
- B21’s position after $ m $ moves: $ 1 + m \cdot V_b \mod N $
- Lowie’s position after $ m $ moves: $ 1 + m \cdot V_l \mod N $
At roll $ t $:
- If $ t \equiv 1 \pmod{3} $, Seo moves: check if $ 1 + r \cdot V_s \mod N \in \text{owned by B21 or Lowie} $
- If $ t \equiv 2 \pmod{3} $, B21 moves: check if $ 1 + r \cdot V_b \mod N \in \text{owned by Seo or Lowie} $
- If $ t \equiv 0 \pmod{3} $, Lowie moves: check if $ 1 + r \cdot V_l \mod N \in \text{owned by Seo or B21} $
Ownership:
- A player owns a property the first time they land on it (excluding position 1).
- Position 1 is never owned.
Define:
Let $ S = \{ (1 + i \cdot V_s) \mod N + 1 \mid i = 0, 1, \dots, 10^9 - 1 \} \setminus \{1\} $
Let $ B = \{ (1 + i \cdot V_b) \mod N + 1 \mid i = 0, 1, \dots, 10^9 - 1 \} \setminus \{1\} $
Let $ L = \{ (1 + i \cdot V_l) \mod N + 1 \mid i = 0, 1, \dots, 10^9 - 1 \} \setminus \{1\} $
Find minimal $ t \in [1, 3 \times 10^9] $ such that:
- If $ t \equiv 1 \pmod{3} $, then $ (1 + \frac{t-1}{3} \cdot V_s) \mod N + 1 \in B \cup L $
- If $ t \equiv 2 \pmod{3} $, then $ (1 + \frac{t-2}{3} \cdot V_b) \mod N + 1 \in S \cup L $
- If $ t \equiv 0 \pmod{3} $, then $ (1 + \frac{t}{3} - 1 \cdot V_l) \mod N + 1 \in S \cup B $
Return the smallest such $ t $, or $ 3000000000 $ if none exists.