There are N jobs (labeled from 1 to N) that you have to schedule, and some jobs are related to other jobs. For example, if job No.3 is related to job No.2, then job No.3 can only be done after job No.2 is done.
Output the number of all possible scheduling.
The first line contains a positive integer T (T <= 20), which indicates how many cases in the input.
Each case starts with two positive integers N and M (1 <= N <= 10), and N denotes the amount of the job. The next M lines contain the relationship among jobs. Each line contains two positive integers A and B, separated by a single space, denoting A is related to B.
Each case is separated by a blank line.
The output contains one line for each test case. Each line contains an integer, which is the number of all possible ways.