Pizza!

Time limit1sMemory limit128 MB

Summary

Given nuggets at polar positions on a unit circle, find the maximum number of equal-angle radial slices so every slice holds the same nugget count.

Level: Medium6 of 10
Topics: Math, Number theory, Geometry, Sorting
Solved: No attempts yet

Problem

The results have all been announced, and it is finally time for the most important part of the contest: eating pizza.

But the pizza is shaped so oddly that we have to write code again.

The pizza is a circle of radius $1$ , and a few nuggets sit on top of it.

When cutting the pizza, all three of the following conditions must hold:

Every cut must run along a radius, from the center of the pizza straight out to the edge.
No nugget may ever be cut.
After all cuts are made, every resulting piece must be the same size, and every piece must hold the same number of nuggets.

Even though the contest is over, a fight is about to break out over mere nuggets. Since there are many participants, you want to cut the pizza into as many pieces as possible. Determine the maximum number of pieces the pizza can be cut into while satisfying the conditions above.

You may also choose not to cut the pizza at all. In that case the pizza is a single piece.

Input

The first line contains the number of test cases $K$ .

The first line of each test case contains the number of nuggets $N$ ( $1 \le N \le 200$ ).

Each of the next $N$ lines gives the position of one nugget as two real numbers $\alpha$ and $r$ , separated by a space.

$\alpha$ is the angle measured counterclockwise from the center of the pizza and satisfies $0 \le \alpha < 2\pi$ .

$r$ is the distance from the center of the pizza to the nugget and satisfies $0 < r \le 1$ . (The pizza has radius $1$ .)

A nugget is treated as a single point with no size, and no two nuggets occupy exactly the same position (though two nuggets may share the same angle $\alpha$ while differing in distance $r$ ).

Output

For each test case, first print Data Set K: (where $K$ is the test case number), then print s slices where $s$ is the maximum number of pieces the pizza can be cut into.

For example, if the answer for the first test case is $1$ , print Data Set 1: 1 slices.

Print one blank line between the outputs of consecutive test cases.

Hint

Do not worry about grammatical awkwardness in the output (for instance, printing 1 slices even for a single piece).

Examples6

Example 1

Input

2
2
1.57 0.5
1.57 0.7
4
0.7 0.9
1.5 0.1
1.8 0.5
3.05 1.0

Expected output

Data Set 1: 1 slices

Data Set 2: 2 slices

Example 2
Input
```
1
1
2.0 0.5
```
Expected output
```
Data Set 1: 1 slices
```

Example 3

Input

1
4
0.5 0.5
2.0 0.4
3.5 0.6
5.0 0.9

Expected output

Data Set 1: 4 slices

Example 4

Input

1
3
1.0 0.5
1.1 0.6
1.2 0.7

Expected output

Data Set 1: 1 slices

Example 5

Input

Expected output

Data Set 1: 2 slices

Example 6

Input

1
3
0.5 0.5
2.5 0.5
4.5 0.5

Expected output

Data Set 1: 3 slices