You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

乐高是最受孩子们欢迎的玩具之一。孩子们可以用乐高积木制作不同种类的玩具。

烤乐滋的老师准备买一些乐高作为礼物送给孩子们，在送给孩子之前，烤乐滋的老师自己体验了一下搭积木的快乐。在拼乐高的过程中，突然想到一个问题。

如果现在给你 $k$ 个 $1\times 1$ 的小正方形的乐高积木，和 $1$ 个 $n \times m$ 的大矩形积木底座。你需要将这些 $k$ 个小正方形全部搭建在 $n \times m$ 的矩形底座上，问可以用这些小方块做出多少个不同形状的乐高图形？

注意，你搭建出来的图形需要满足以下要求：

1. 乐高图形必须是连通的，不能有单独的一块。
2. 所有能够通过平移、旋转、镜像翻转操作变成一样的图形，认为是相同的。
3. $k$ 个小方块必须用完。

.#   #.   ##   ##
##   ##   #.   .#

从左到右分别对应图 $1 \sim 4$。

其中：

• 图 2 可以通过图 1 左右翻转得到；
• 图 3 可以通过图 1 旋转 $180$ 度得到；
• 图 4 可以通过图 1 上下翻转得到。

对于下面数据中的一组数据 $k=3,n=3,m=2$，有且仅有如下 $2$ 种情况，黑色的为 $1\times 1$ 的小方块，白色的就是 $3 \times 2$ 的底座，我们会在底座上拼图。

...   .#.
###   ##.

黑色代表 #，白色代表 .。

输入格式

第一行一个整数 $T$，表示数据组数。

接下来有 $T$ 行，每行三个整数 $k,n,m$ 分别表示小方块的数量，以及矩形底座的长和宽，整数之间以空格隔开。

输出格式

输出共 $T$ 行。

每一行，输出一个整数表示可以用 $k$ 小方块在 $n \times m$ 矩形底座上搭建出来的乐高图形的数量，搭建出来的图形要满足题目要求。

样例 #1

样例输入 #1

5
5 1 4
1 1 1
3 3 1
3 3 2
5 5 5

样例输出 #1

0
1
1
2
12

提示

【样例部分数据解释】

样例中的第一组数据 5 1 4，显然，$5$ 个小方块无法放入 $1\times 4$ 的矩形中，所输出 $0$；

样例中的第二、三组数据 1 1 1 和 3 3 1，显然只有全部填满这一种方案。

样例中的第四种数据 3 3 2 只有两种情况，参考题面描述。

【数据范围】

本题共 $20$ 个测试点，对于全部数据满足 $1 \le T \le 10^5,1 \le k \le 10,1 \le n,m\le k$。

具体数据分布情况如下表格：

第 $1$ 个点分值 $81$ 分，其余点各 $1$ 分。