在 $$$n$$$ 不同点 $$$(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$$$ 处有 $$$n$$$ 塔,因此没有三个共线,也没有四个共循环。最初,您拥有塔 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$,并且您想占领所有塔。为此,您可以多次执行以下操作:
- 选择两座你拥有的塔 $$$P$$$ 和 $$$Q$$$ 以及一座你不拥有的塔 $$$R$$$,这样穿过 $$$P$$$、$$$Q$$$ 和 $$$R$$$ 的圆圈包含其内部的所有 $$$n$$$ 塔。
- 然后,占领三角形 $$$\triangle PQR$$$ 内或之上的所有塔,包括 $$$R$$$ 本身。
计算最小长度的攻击计划的数量。请注意,可能无法占领所有塔楼,在这种情况下答案为 $$$0$$$。
由于答案可能很大,因此输出它对 $$$998\,244\,353$$$ 取模。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 250$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$4 \leq n \leq 100$$$) — 塔的数量。
接下来的 $$$n$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$-10^4 \leq x_i, y_i \leq 10^4$$$) — 第 $$$i$$$ 塔的位置。最初,您拥有塔 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$。
所有塔都位于不同的位置,没有三座塔共线,也没有四座塔共圆。
所有测试用例的 $$$n$$$ 总和不超过 $$$1000$$$。
输出
对于每个测试用例,输出一个整数 - 捕获所有塔后最小长度的攻击计划的数量,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
3 5 1 1 2 5 3 3 4 2 5 4 6 1 1 3 3 1 2 2 1 3 10000 19 84 7 2 7 -4 -3 -3 6 3 1 -5 2 1 -4 -1 7
输出 #1
1 0 10
注意
在第一个测试用例中,只有一个可能的最短长度的攻击计划,如下所示。
- 使用 $$$P =$$$ tower $$$1$$$、$$$Q =$$$ tower $$$2$$$ 和 $$$R =$$$ tower $$$5$$$ 的操作。通过这三座塔的圆圈包含其内部的所有塔,因此塔 $$$3$$$ 和 $$$5$$$ 被占领。
- 使用 $$$P =$$$ tower $$$5$$$、$$$Q =$$$ tower $$$1$$$ 和 $$$R =$$$ tower $$$4$$$ 的操作。穿过这三座塔的圆圈包含其内部的所有塔,因此塔 $$$4$$$ 被占领。
例如,在第二种情况下,你永远无法占领$$$(3, 10\,000)$$$处的塔。