Processing math: 100%

Задача 1. Новый год в детском саду

Входной файл:Стандартный вход   Ограничение времени:2 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

В детском саду готовятся к новому году, и воспитательница !A !B !C решила организовать детей, чтобы они подготовили украшения и отправили их Санте Клаусу для украшения своих оленей.

Дети с интересом восприняли идею и вырезали из бумаги a звездочек и b снежинок. Теперь они планируют отправить их Санте Клаусу по почте. Им так понравились вырезанные ими украшения, что они, возможно, решат оставить себе часть. Таким образом, дети могут отправить Санте x звездочек и y снежинок, где 0xa и 0yb. Чтобы Санта не расстроился, дети должны отправить ему хотя бы одно украшение. То есть должно выполняться также условие x+y>0.

Чтобы все олени выглядели красиво, на каждом должно оказаться одинаковое количество украшений. Известно, что у Санты n оленей, поэтому если будут отправлены x звездочек и y снежинок, величина x+y должна делиться на n.

Воспитательница заинтересовалась: а сколько есть всего различных способов составить посылку Санте Клаусу. Два способа считаются различными, если в них отличается количество звездочек или количество снежинок.

Формат входных данных

В одном наборе входных данных содержатся несколько тестов. Каждый тест следует решить независимо.

Первая строка входных данных содержит целое число t — количество тестов (1t105).

Следующие строки описывают тесты, по одному на строке. Описание теста состоит из трех целых чисел n, a и b — количество оленей у Санты, количество звездочек и количество снежинок, вырезанных детьми (4n109; 0a,b109).

Формат выходных данных

Выведите t чисел. Для каждого теста выведите одно число: количество способов составить посылку для Санты Клауса.

Ограничения

1t105

4n109; 0a,b109

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Доп. ограничения Необходимые подзадачи Информация о проверке
1 10 t=1, a,b1000 первая ошибка
2 10 t1000, a=0 первая ошибка
3 15 t1000, a,b<n1000 первая ошибка
4 10 t1000, a,b1000 1, 3 первая ошибка
5 15 t=1, n1000 первая ошибка
6 10 t1000, n1000 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
4
4 2 2
4 4 4
6 5 5
8 13 17
1
6
5
30

0.062s 0.010s 13