A polygon is a two dimension figure defined by a chain of line segments that form a closed loop (a polygon must have a non-zero area); it is conventional to write a polygon as a sequence of its vertices. For example, we can define a right-triangle with the point sequence {(0, 0), (0, 1), (1, 0)}. A simple polygon is one which does not cross over itself.

Given a set of points, can you count the number of simple polygons that can be formed using only points from this set?

Input

The input will begin with a line containing a single positive integer t representing the number of test cases you must process. The first line of each test case is N, the number of points (1 ≤ N ≤ 9). Following will be N lines each specifying a point by its x and y co-ordinates which are guaranteed to be integers. You are guaranteed that no three points will be collinear (no line can be drawn through three points).

Output

For each test case print the number of simple polygons that can be formed on its own line.

Example

Input:
1
4
0 0
0 1
1 0
1 1

Output:
5