Joyboard
Contest: Codeforces Round 902 (Div. 2, based on COMPFEST 15 - Final Round)
Difficulty rating: 1200
Tags: 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$$$?

Input format:
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.

Output format:
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$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
4
4 6 3
2 0 1
265 265 265
3 10 2

Example output:
2
1
0
5

Editorial:
There are only a few cases.
1. If $$$a_{n+1}=0$$$, then every value of $$$a_i$$$ is $$$0$$$. So there is only $$$1$$$ distinct value.
2. If $$$1\leq a_{n+1}\leq n$$$, then there exists an index $$$p$$$ ($$$p=a_{n+1}$$$) such that $$$a_i=a_{n+1}$$$ for all indices $$$p+1\leq i\leq n+1$$$ and $$$a_i=0$$$ for all $$$1\leq i\leq p$$$. So there are $$$2$$$ distinct values.
3. If $$$a_{n+1}>n$$$ and $$$a_{n+1}$$$ is divisible by $$$n$$$, then $$$a_n=0$$$ and all values to the left of that are also $$$0$$$. So there are $$$2$$$ distinct values.
4. If $$$a_{n+1}>n$$$ and $$$a_{n+1}$$$ is not divisible by $$$n$$$, then $$$1\leq a_n\leq n-1$$$. This is is equivalent to case 2, which means that there are $$$2$$$ distinct values from index $$$1$$$ to $$$n$$$. So in total, there are $$$3$$$ distinct values.
So the number of ways is as follows:
• If $$$k=1$$$, there is always $$$1$$$ way, since $$$m\geq0$$$.
• If $$$k=2$$$ and $$$m\leq n$$$, there are $$$m$$$ ways.
• If $$$k=2$$$ and $$$m>n$$$, there are $$$n+\lfloor\frac{m-n}{n}\rfloor$$$.
• If $$$k=3$$$ and $$$m\leq n$$$, there are $$$0$$$ ways.
• If $$$k=3$$$ and $$$m>n$$$, there are $$$m-n-\lfloor\frac{m-n}{n}\rfloor$$$.
• If $$$k>3$$$, there are $$$0$$$ ways.
Time complexity for each test case: $$$O(1)$$$