logo AlgoBeat OnlineJudge
登录 注册

#10097. 食堂盒饭

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: AlgoBeat 官方账号

题目描述

学校食堂今天供应两种主食:米饭(共 份)和面条(共 份)。
午饭时间,食堂阿姨要把这些主食装进外卖盒里,每个外卖盒必须恰好装 份主食(可以是米饭和面条的任意组合),而且至少要装一盒才能送出去(不能空手而归)。
阿姨可以从现有库存中取出任意数量的米饭和面条(但不能超过库存),然后装成若干个满盒。
现在阿姨想知道:有多少种不同的取货方式,使得取出的主食总数能被 整除,并且总数大于
如果两种方式中,取走的米饭数量不同,或者取走的面条数量不同,就视为不同的方式。

注意:盒饭本身不区分顺序,只看每种主食取了多少份。

输入格式

第一行一个整数 ),表示数据组数。
接下来 行,每行三个整数 ),分别表示:

  • :每个外卖盒必须装的主食份数;
  • :米饭的库存份数;
  • :面条的库存份数。

输出格式

对于每组数据,输出一行一个整数,表示满足条件的取货方案总数。

样例

样例输入

4
4 2 2
4 4 4
6 5 5
8 13 17

样例输出

1
6
5
30

数据范围与提示

样例解释

  • 第一组:米饭 份、面条 份,要凑成 的倍数且大于 。唯一方案是取走 份米饭和 份面条(共 份),答案为
  • 第二组:各有 份,总份数可为 。取 份有 种(米饭 ,面条对应 ),取 份只有 种(全部取走),共 种。
  • 第三组:各 份,要凑 的倍数,只有 份可行(取 份超过库存)。满足 的方案为 ,共 种。
  • 第四组:各 ,总和可为
    和为 种;和为 种;和为 种;总计 种。

数据范围