Новый год в детском саду
(Время: 1 сек. Память: 32 Мб Сложность: 28%)
В детском саду готовятся к новому году, и воспитательница Яна Константиновна Снегурочкина решила организовать детей, чтобы они подготовили украшения и отправили их Санте Клаусу для украшения своих оленей.
Дети с интересом восприняли идею и вырезали из бумаги a звездочек и b снежинок. Теперь они планируют отправить их Санте Клаусу по почте. Им так понравились вырезанные ими украшения, что они, возможно, решат оставить себе часть. Таким образом, дети могут отправить Санте x звездочек и y снежинок, где 0 ≤ x ≤ a и 0 ≤ y ≤ b. Чтобы Санта не расстроился, дети должны
отправить ему хотя бы одно украшение. То есть должно выполняться также условие x + y > 0.
Чтобы все олени выглядели красиво, на каждом должно оказаться одинаковое количество украшений. Известно, что у Санты n оленей, поэтому если будут отправлены x звездочек и y снежинок, величина x + y должна делиться на n.
Воспитательница заинтересовалась: а сколько есть всего различных способов составить посылку Санте Клаусу. Два способа считаются различными, если в них отличается количество звездочек или количество снежинок.
Входные данные
Во входном файле INPUT.TXT содержатся несколько тестов. Каждый тест следует решить независимо.
Первая строка входных данных содержит целое число t – количество тестов (1 ≤ t ≤ 105).
Следующие строки описывают тесты, по одному на строке. Описание теста состоит из трех целых чисел n, a и b – количество оленей у Санты, количество звездочек и количество снежинок, вырезанных детьми (4 ≤ n ≤ 109; 0 ≤ a, b ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите t чисел по одному на строке: для каждого теста одно число – количество способов составить посылку для Санты Клауса.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
4 2 2
4 4 4
6 5 5
8 13 17 | 1
6
5
30 |
Пояснение
В первом тесте у Санты 4 оленя, а дети вырезали 2 звездочки и 2 снежинки. Здесь подходит только один набор – нужно отправить все вырезанные украшения.
Во втором тесте у Санты также 4 оленя, но дети вырезали 4 звездочки и 4 снежинки. Здесь подходит 6 наборов: 0 звездочек и 4 снежинки, 1 звездочка и 3 снежинки, 2 звездочки и 2 снежинки, 3 звездочки и 1 снежинка, 4 звездочки и 0 снежинок, а также 4 звездочки и 4 снежинки.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
