Alice 和 Bob 决定发明一种基于质数的新型加密货币，名为“互联网最酷质数币”（Internet’s Coolest PrimeCoin）。这是一个绝对绝妙的主意，绝不可能出任何差错。

提醒一下，质数是指大于 1 且除了 1 和它本身以外没有其他约数的整数。在现代数学中，1 不被视为质数。

经过几个月的计算和对云服务器的肆意滥用，Alice 和 Bob 终于计算出了前 $n$ 个质数。这些质数将作为该加密货币工作量证明（Proof of Work）的基础……某种程度上是这样。我们并不了解具体细节。

总之！现在我们必须决定这前 $n$ 个质数分别归谁所有。对于每一个质数，你必须将其分配给 Alice 或 Bob。一个都不能丢，毕竟他们为了这些质数付出了巨大的努力！我们希望分配这些质数，使得 Alice 和 Bob 各自得到的总价值与他们各自对项目的贡献成比例。

设 $A$ 为分配给 Alice 的质数之和，$B$ 为分配给 Bob 的质数之和。Alice 和 Bob 决定，按照 $p : q$ 的比例分配总价值是公平的。因此，如果 $A : B = p : q$，则该质数分配方案被认为是公平的。由于他们今天心情格外好，题目保证 $p$ 和 $q$ 也是质数。

给定 $n$、$p$ 和 $q$，计算将前 $n$ 个质数公平分配给 Alice 和 Bob 的不同方案数。如果某个质数在一种方案中分配给了 Alice，而在另一种方案中分配给了 Bob，则认为这两种方案不同。答案可能非常大，因此我们仅要求输出答案对 1169996969 取模的结果。此外，每个文件中包含 $T$ 个独立的测试用例。

输入格式

输入的第一行包含一个正整数 $T$。

接下来有 $T$ 行，每行包含三个空格分隔的整数 $n$、$p$ 和 $q$，表示对于该测试用例，需要将前 $n$ 个质数分配给 Alice 和 Bob，使得总价值之比为 $p : q$。

数据范围

• $1 \le T \le 10^5$
• $2 \le n \le 2000$
• $2 \le p, q \le 30$
• $p$ 和 $q$ 为质数

输出格式

对于每个测试用例，输出一个整数，表示将前 $n$ 个质数公平分配给 Alice 和 Bob 的方案数。由于答案可能非常大，你只需要输出其对 1169996969 取模的结果。

样例

输入 1

2
3 7 7
8 2 5

输出 1

2
4

输入 2

3
1859 19 7
1967 2 17
2000 29 29

输出 2

213519321
1086566377
0

说明

前三个质数是 $\{2, 3, 5\}$。要以 $7 : 7$ 的比例分配这些质数，我们可以将 $\{2, 3\}$ 分给 Alice，将 $\{5\}$ 分给 Bob；或者将 $\{5\}$ 分给 Alice，将 $\{2, 3\}$ 分给 Bob。

前八个质数是 $\{2, 3, 5, 7, 11, 13, 17, 19\}$。要以 $2 : 5$ 的比例分配这些质数，我们可以……

• 将 $\{3, 19\}$ 分给 Alice，将 $\{2, 5, 7, 11, 13, 17\}$ 分给 Bob。
• 将 $\{5, 17\}$ 分给 Alice，将 $\{2, 3, 7, 11, 13, 19\}$ 分给 Bob。
• 将 $\{2, 3, 17\}$ 分给 Alice，将 $\{5, 7, 11, 13, 19\}$ 分给 Bob。
• 将 $\{2, 7, 13\}$ 分给 Alice，将 $\{3, 5, 11, 17, 19\}$ 分给 Bob。