From 2011 facebook is organizing a Facebook hacker cup every year around feb, visit Facebook hacker cup homepage for more details

This question is the third question(Carried 45 marks out of 100) for the Round 2 of 2013 hacker cup. only top 100 contestants will be moved to Round 3.

## Problem Statement

In this problem you need to count number of possible permutations **p** of the first **N** integers, given **N-1** constraints of the form **p _{i} < p_{j}.**

## Input

The first line contains an integer **T**, **T** ≤ 20, followed by **T** test cases. Each test case begins with an integer **N**, **N** ≤ 1000, which is the number of integers in the permutation. The next **N – 1** lines each contain a single constraint in the following format: “**i** **sign** **j**“, where 0 ≤ **i**, **j** ≤ **N – 1** and **sign** is either “**<**” or “**>**“, which denotes whether the **i**-th element of the permutation should be less than or greater than the **j**-th element.

It is guaranteed that it is not possible to partition indices into two disjoint sets A and B such that there is no constraint involving elements from both A and B.

[Read more…]