| 问题描述 |
|---|
我国古代数学家张丘建在《算经》一书中提出的数学问题：鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、鸡母、鸡雏各几何？ 显然这个问题的答案是固定的，于是我们稍微改一下，n 钱买 n 鸡，有多少种不同的买法？ 任意两种买法视为不同当且仅当鸡翁或鸡母或鸡雏中任一数量不同。 |
| 输入描述 |
第一行是一个正整数 T 代表测试案例的数量。（1 ≤ T ≤ 100） 每组案例包含一个正整数 n 表示钱数和鸡数。 测试用例1：1 ≤ n ≤ 100 测试用例2：1 ≤ n ≤ 1500 测试用例3：1 ≤ n ≤ 2e6 测试用例4：1 ≤ n ≤ 2e7 测试用例5：1 ≤ n ≤ 1e18 |
| 输出描述 |
对于每组案例，输出一个整数表示答案，然后换行。 |
| 样例输入复制样例 |
2 3 100 |
| 样例输出 |
0 4 |
| 提示说明 |
n = 100 时的买法： 0 25 75 4 18 78 8 11 81 12 4 84 |
| 相关 |