C. Джойборд
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Чанека, прирождённый геймер, изобрела новый игровой контроллер под названием «Джойборд». Интересно, что изобретенный ею джойборд можно использовать только для одной игры.

На джойборде имеется экран, содержащий $$$n+1$$$ слотов, пронумерованных от $$$1$$$ до $$$n+1$$$ слева направо. Все $$$n+1$$$ слотов заполняются массивом целых неотрицательных чисел $$$[a_1,a_2,a_3,\ldots,a_{n+1}]$$$. Чанека, как игрок, должна присвоить $$$a_{n+1}$$$ целое число от $$$0$$$ до $$$m$$$ включительно. Тогда для каждого $$$i$$$ от $$$n$$$ до $$$1$$$ значение $$$a_i$$$ будет равно остатку от деления $$$a_{i+1}$$$ (соседнего справа значения) на $$$i$$$. Другими словами, $$$a_i = a_{i + 1} \bmod i$$$.

Чанека хочет, чтобы после присвоения каждому слоту целого числа на всем экране (среди всех слотов $$$n+1$$$) было ровно $$$k$$$ различных значений. Сколько существует допустимых способов присвоения целого неотрицательного числа слоту $$$n+1$$$?

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 2\cdot10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \leq n \leq 10^9$$$; $$$0 \leq m \leq 10^9$$$; $$$1 \leq k \leq n+1$$$): всего имеется $$$n+1$$$ слотов, значение в слоте $$$n+1$$$ не должно быть больше $$$m$$$, и в итоговом массиве должно быть ровно $$$k$$$ различных значений.

Выходные данные

Для каждого набора входных данных в отдельной строке выведите количество допустимых способов присвоения целого неотрицательного числа в слот $$$n+1$$$.

Пример
Входные данные
4
4 6 3
2 0 1
265 265 265
3 10 2
Выходные данные
2
1
0
5
Примечание

В первом наборе входных данных одним из $$$2$$$ возможных способов для Чанеки является выбор $$$a_{n+1}=6$$$. Если она это сделает, то:

  • $$$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]$$$
  • Существует $$$3$$$ различных значения.

Во втором наборе входных данных для Чанеки возможен $$$1$$$ вариант — выбрать $$$a_{n+1}=0$$$. Если она это сделает, то $$$a = [0, 0, 0]$$$. Существует только $$$1$$$ значение.

В третьем наборе входных данных не существует возможного способа присвоения целого неотрицательного числа в слот $$$n+1$$$.