题目背景

老师准备了若干块积木，并组织了一场搭建高塔的游戏。一座高塔由若干层组成，每一层横向摆放一定数量的积木。为了让高塔的轮廓保持规律，相邻两层的积木数量必须恰好相差一块。

题目描述

现有至多 $N$ 块积木，需要搭建一座恰好有 $H$ 层的高塔。

规定最底层放置 $M$ 块积木。对于其上方的每一层，该层积木数量必须比它正下方一层的积木数量恰好多 $1$ 块或少 $1$ 块。

每一层都必须至少放置一块积木，整座高塔使用的积木总数不能超过 $N$。

请计算一共有多少种不同的高塔。

若两座高塔至少存在一层的积木数量不同，则认为它们是不同的高塔。

输入格式

第一行包含一个整数 $T$，表示测试用例数量。

接下来 $T$ 行，每行包含三个正整数 $N,H,M$，分别表示可使用的积木数量上限、高塔层数以及最底层的积木数量。

输出格式

对于每组测试用例，输出一行一个整数，表示满足要求的高塔数量。

样例输入

2
7 3 2
22 5 4

样例输出

2
10

样例说明

对于第一组测试用例，两种高塔从底层到顶层的每层积木数量依次为：

• $2,1,2$；
• $2,3,2$。

数据范围

对于所有测试数据：

• $1\le T\le 1001$；
• $1\le N\le 32767$；
• $1\le H\le 60$；
• $1\le M\le 10$。

答案保证可以用有符号 $64$ 位整数表示。