Farmer Jiang has n (1 ≤ n ≤ 200) cows. He loves the cows so much that for every single cow he prepares a huge “food court” – actually it’s an area fulfilled with foods and drinks. There are exactly n food courts, with distinct themes.
Everyday Farmer Jiang takes his cows to the food courts and put exactly one cow in one food court. He knows that some cows is favoring with some specific food court. He does not want to see cows feeling sad, so he decided only taking the cows into one of their favored food courts.
In how many ways that Farmer Jiang can let his cows pick favored food court and each food court is having at most one cow? Farmer Jiang knows that there are always less than 200,000 possible configurations in total.
The file begins with an integer T (T ≤ 25) indicating the number of test cases follows. For each test case, first line contains two integers n, m (1 ≤ n ≤ 200, 1 ≤ m ≤ n^2). Each of the next m lines contains 2 integers u, v (1 ≤ u, v ≤ n) means that u-th cow loves v-th food court. You may assume each (u, v) pair in a single test case never occurs more than once. There may be white spaces and empty lines everywhere in the input file.
For each test case, please output “Case #x:” with x being the case number starting from 1 and output the number of total ways.