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

Дети с интересом восприняли идею и вырезали из бумаги $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$ чисел. Для каждого теста выведите одно число: количество способов составить посылку для Санты Клауса.

Подзадачи