UF2015A - Simple Polygon

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

Added by:Cormac
Date:2015-02-19
Time limit:1s-4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:UF High School Programming Contest 2015

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.