题目描述

译自 ROI Regional 2022 Day2 T1. Новый год в детском саду

幼儿园正在为新年做准备，老师决定组织孩子们制作装饰品并寄给圣诞老人，用来装饰他的驯鹿。

孩子们对这个主意很感兴趣，他们用纸剪了 $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)$，分别表示圣诞老人的驯鹿数量、孩子们剪的星星数量和雪花数量。

输出格式

对于每组输入数据，输出一个整数，表示有多少种方式可以组成寄给圣诞老人的包裹。

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$ 片雪花。

数据范围与提示

详细子任务附加限制及分值如下表所示。