Входной файл: | Стандартный вход | Ограничение времени: | 2 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
Максимальный балл: | 100 |
В детском саду готовятся к новому году, и воспитательница !A !B !C решила организовать детей, чтобы они подготовили украшения и отправили их Санте Клаусу для украшения своих оленей.
Дети с интересом восприняли идею и вырезали из бумаги a звездочек и b снежинок. Теперь они планируют отправить их Санте Клаусу по почте. Им так понравились вырезанные ими украшения, что они, возможно, решат оставить себе часть. Таким образом, дети могут отправить Санте x звездочек и y снежинок, где 0≤x≤a и 0≤y≤b. Чтобы Санта не расстроился, дети должны отправить ему хотя бы одно украшение. То есть должно выполняться также условие x+y>0.
Чтобы все олени выглядели красиво, на каждом должно оказаться одинаковое количество украшений. Известно, что у Санты n оленей, поэтому если будут отправлены x звездочек и y снежинок, величина x+y должна делиться на n.
Воспитательница заинтересовалась: а сколько есть всего различных способов составить посылку Санте Клаусу. Два способа считаются различными, если в них отличается количество звездочек или количество снежинок.
В одном наборе входных данных содержатся несколько тестов. Каждый тест следует решить независимо.
Первая строка входных данных содержит целое число t — количество тестов (1≤t≤105).
Следующие строки описывают тесты, по одному на строке. Описание теста состоит из трех целых чисел n, a и b — количество оленей у Санты, количество звездочек и количество снежинок, вырезанных детьми (4≤n≤109; 0≤a,b≤109).
Выведите t чисел. Для каждого теста выведите одно число: количество способов составить посылку для Санты Клауса.
1≤t≤105
4≤n≤109; 0≤a,b≤109
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Доп. ограничения | Необходимые подзадачи | Информация о проверке |
---|---|---|---|---|
1 | 10 | t=1, a,b≤1000 | первая ошибка | |
2 | 10 | t≤1000, a=0 | первая ошибка | |
3 | 15 | t≤1000, a,b<n≤1000 | первая ошибка | |
4 | 10 | t≤1000, a,b≤1000 | 1, 3 | первая ошибка |
5 | 15 | t=1, n≤1000 | первая ошибка | |
6 | 10 | t≤1000, n≤1000 | 3, 5 | первая ошибка |
7 | 30 | нет | 1 — 6 | первая ошибка |
В первом тесте у Санты 4 оленя, а дети вырезали 2 звездочки и 2 снежинки. Здесь подходит только один набор — нужно отправить все вырезанные украшения.
Во втором тесте у Санты также 4 оленя, но дети вырезали 4 звездочки и 4 снежинки. Здесь подходит 6 наборов: 0 звездочек и 4 снежинки, 1 звездочка и 3 снежинки, 2 звездочки и 2 снежинки, 3 звездочки и 1 снежинка, 4 звездочки и 0 снежинок, а также 4 звездочки и 4 снежинки.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|