Задача №115202. Новый год в детском саду
В детском саду готовятся к новому году, и воспитательница решила организовать детей, чтобы они подготовили украшения и отправили их Санте Клаусу для украшения своих оленей.
Дети с интересом восприняли идею и вырезали из бумаги \(a\) звездочек и \(b\) снежинок. Теперь они планируют отправить их Санте Клаусу по почте. Им так понравились вырезанные ими украшения, что они, возможно, решат оставить себе часть. Таким образом, дети могут отправить Санте \(x\) звездочек и \(y\) снежинок, где \(0 \le x \le a\) и \(0 \le y \le b\). Чтобы Санта не расстроился, дети должны отправить ему хотя бы одно украшение. То есть должно выполняться также условие \(x + y > 0\).
Чтобы все олени выглядели красиво, на каждом должно оказаться одинаковое количество украшений. Известно, что у Санты \(n\) оленей, поэтому если будут отправлены \(x\) звездочек и \(y\) снежинок, величина \(x+y\) должна делиться на \(n\).
Воспитательница заинтересовалась: а сколько есть всего различных способов составить посылку Санте Клаусу. Два способа считаются различными, если в них отличается количество звездочек или количество снежинок.
В одном наборе входных данных содержатся несколько тестов. Каждый тест следует решить независимо.
Первая строка входных данных содержит целое число \(t\) — количество тестов (\(1 \le t \le 10^5\)).
Следующие строки описывают тесты, по одному на строке. Описание теста состоит из трех целых чисел \(n\), \(a\) и \(b\) — количество оленей у Санты, количество звездочек и количество снежинок, вырезанных детьми (\(4 \le n \le 10^9\); \(0 \le a, b \le 10^9\)).
Выведите \(t\) чисел. Для каждого теста выведите одно число: количество способов составить посылку для Санты Клауса.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Доп. ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 10 | \(t = 1\), \(a, b \le 1000\) | первая ошибка | |
| 2 | 10 | \(t \le 1000\), \(a = 0\) | первая ошибка | |
| 3 | 15 | \(t \le 1000\), \(a, b \lt n \le 1000\) | первая ошибка | |
| 4 | 10 | \(t \le 1000\), \(a, b \le 1000\) | 1, 3 | первая ошибка |
| 5 | 15 | \(t = 1\), \(n \le 1000\) | первая ошибка | |
| 6 | 10 | \(t \le 1000\), \(n \le 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 снежинки.
4 4 2 2 4 4 4 6 5 5 8 13 17
1 6 5 30