Codeforces Global Round 26 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

geometry

*3300

No tag edit access

The problem statement has recently been changed. View the changes.

×
H. Tower Capturing

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere are $$$n$$$ towers at $$$n$$$ distinct points $$$(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$$$, such that no three are collinear and no four are concyclic. Initially, you own towers $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$, and you want to capture all of them. To do this, you can do the following operation any number of times:

- Pick two towers $$$P$$$ and $$$Q$$$ you own and one tower $$$R$$$ you don't own, such that the circle through $$$P$$$, $$$Q$$$, and $$$R$$$ contains all $$$n$$$ towers inside of it.
- Afterwards, capture all towers in or on triangle $$$\triangle PQR$$$, including $$$R$$$ itself.

Count the number of attack plans of minimal length. Note that it might not be possible to capture all towers, in which case the answer is $$$0$$$.

Since the answer may be large, output it modulo $$$998\,244\,353$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 250$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$4 \leq n \leq 100$$$) — the number of towers.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^4 \leq x_i, y_i \leq 10^4$$$) — the location of the $$$i$$$-th tower. Initially, you own towers $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$.

All towers are at distinct locations, no three towers are collinear, and no four towers are concyclic.

The sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Output

For each test case, output a single integer — the number of attack plans of minimal length after which you capture all towers, modulo $$$998\,244\,353$$$.

Example

Input

351 12 53 34 25 461 13 31 22 13 1000019 8472 7-4 -3-3 63 1-5 21 -4-1 7

Output

1 0 10

Note

In the first test case, there is only one possible attack plan of shortest length, shown below.

- Use the operation with $$$P =$$$ tower $$$1$$$, $$$Q =$$$ tower $$$2$$$, and $$$R =$$$ tower $$$5$$$. The circle through these three towers contains all towers inside of it, and as a result towers $$$3$$$ and $$$5$$$ are captured.
- Use the operation with $$$P =$$$ tower $$$5$$$, $$$Q =$$$ tower $$$1$$$, and $$$R =$$$ tower $$$4$$$. The circle through these three towers contains all towers inside of it, and as a result tower $$$4$$$ is captured.

In the second case, for example, you can never capture the tower at $$$(3, 10\,000)$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/18/2024 10:39:19 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|