Convex Hull

Time Limit: 2 Seconds
Memory Limit: 65536 KB

Edward has `n` points on the plane. He picks a subset of points (at least three points), and defines the beauty of the subset as twice the area of corresponding convex hull. Edward wants to know summation of the beauty of all possible subsets of points (at least three points).

No two points coincide and no three points are on the same line.

#### Input

There are multiple test cases. The first line of input contains an integer `T` indicating the number of test cases. For each test case:

The first line contains an integer `n` (3 ≤ `n` ≤ 1000). Each of following `n` lines contains 2 integers `x`_{i}, `y`_{i} which denotes a point (`x`_{i}, `y`_{i}) (0 ≤ |`x`_{i}|, |`y`_{i}| ≤ 10^{9}).

The sum of values `n` for all the test cases does not exceed 5000.

#### Output

For each case, if the answer is `S`, output a single integer denotes `S` modulo 998244353.

#### Sample Input

1
3
0 0
0 1
1 0

#### Sample Output

1

Author:

**LIN, Xi**
Source:

**The 12th Zhejiang Provincial Collegiate Programming Contest**
Submit
Status