Game Of Logic

Time Limit: 1 Second    Memory Limit: 32768 KB

This Christmas WishingBone has got some new toys which are real cool. This is one of them.

On a large board there fixed many logic units and lines between them. They are called bone logic which is composed of one input, one output and a nice looking button. Only after the input becomes 1 and the button is pressed will it output 1, otherwise its output is 0. Bone logics can be interconnected in series or in parallel. A legal game board is shown below.

In the figure there are 3 bone logics. The red one and the blue one is interconnected in parallel and they are together interconnected in series with the green one. All the bone logics are arranged so that their input end is on the left and output end is on the right. All the connection points are labeled from 1 to m, where 1 is the single input of the board and m is the single output of the board. Note that an n-to-1 connection point like point 2 in the figure uses AND logic that produces a 1 signal only if all the inputs become 1.

Initially all the signals are 0 except input of the board (point 1). Your goal is to press n bone logics sequentially to turn the output of the board (point m) into 1. A bone can be pressed only if the signal comes into it become 1. And all bones will be pressed exactly once. In the example above, one way to achieve this is to press red-blue-green; another possibility is to press blue-red-green. Though it is rather easy to figure one way out, WishingBone is curious about how many ways on earth he can solve a particular board configuration.

Input

The first line of input is a positive integer N <= 100, which is the number of test cases.

The first line of each case is two integers n and m (0 < n <= 100, 2 <= m <= n+1), which are the number of bone logics and connection points.

The following n lines contains two integers li ri (0 < li, ri <= m) indicating the connection point on the left and right of bone logic i.

The input board configuration is always legal, and has at least one way to achieve the goal.

Output

N integers which are the numbers of ways to achieve the goal on the N board configurations, one per line.

Sample Input

3
3 3
1 2
1 2
2 3
3 4
1 2
2 3
3 4
4 3
1 2
1 2
2 3
1 3

Sample Output

2
1
8

Submit

Source: WishingBone's Contest #1