C. Joyboard
math; number theory
Chaneka, a gamer kid, invented a new gaming controller called joyboard. Interestingly, the joyboard she invented can only be used to play one game.The joyboard has a screen containing \(n+1\) slots numbered from \(1\) to \(n+1\) from left to right. The \(n+1\) slots are going to be filled with an array of non-negative integers \([a_1,a_2,a_3,\ldots,a_{n+1}]\). Chaneka, as the player, must assign \(a_{n+1}\) with an integer between \(0\) and \(m\) inclusive. Then, for each \(i\) from \(n\) to \(1\), the value of \(a_i\) will be equal to the remainder of dividing \(a_{i+1}\) (the adjacent value to the right) by \(i\). In other words, \(a_i = a_{i + 1} \bmod i\).Chaneka wants it such that after every slot is assigned with an integer, there are exactly \(k\) distinct values in the entire screen (among all \(n+1\) slots). How many valid ways are there for assigning a non-negative integer into slot \(n+1\)?
Each test contains multiple test cases. The first line contains an integer \(t\) (\(1 \leq t \leq 2\cdot10^4\)) — the number of test cases. The following lines contain the description of each test case.The only line of each test case contains three integers \(n\), \(m\), and \(k\) (\(1 \leq n \leq 10^9\); \(0 \leq m \leq 10^9\); \(1 \leq k \leq n+1\)) — there are \(n+1\) slots, the integer assigned in slot \(n+1\) must not be bigger than \(m\), and there should be exactly \(k\) distinct values.
For each test case, output a line containing an integer representing the number of valid ways for assigning a non-negative integer into slot \(n+1\).
In the first test case, one of the \(2\) possible ways for Chaneka is to choose \(a_{n+1}=6\). If she does that, then: \(a_4=a_5\bmod 4=6\bmod 4=2\) \(a_3=a_4\bmod 3=2\bmod 3=2\) \(a_2=a_3\bmod 2=2\bmod 2=0\) \(a_1=a_2\bmod 1=0\bmod 1=0\) \(a = [0, 0, 2, 2, 6]\) There are \(3\) distinct values. In the second test case, the \(1\) possible way for Chaneka is to choose \(a_{n+1}=0\). If she does that, then \(a = [0, 0, 0]\). There is only \(1\) distinct value.In the third test case, there is no possible way for assigning a non-negative integer into slot \(n+1\).