Dinner Is Ready

Time Limit: 1 Second    Memory Limit: 32768 KB

Dinner is ready! WishingBone's family rush to the table. WishingBone's mother has prepared many delicious bones. WishingBone has several brothers, namely WishingTwoBones, WishingThreeBones. WishingBone wants at least one bone, WishingTwoBones two and WishingThreeBones three. :-P But as they are not too greedy (or they want to keep shape), they decide that they want at most twice of their minimal requirement. Now let's suppose mother has prepared 7 bones, one way to distribute them is 2-2-3, the other two ways are 1-3-3 and 1-2-4. Of course mother doesn't want to waste any bones, so if she had prepared 13 bones, she would end up without any feasible distribution.

As curious as WishingBone, mother wants to know how many different ways she can distribute those bones.

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 contains two integers n and m (0 < n <= 8, 0 < m), where n is the number of children and m is the number of bones mother has prepared.

The next n lines have two integers mini and maxi (0 <= mini <= maxi <= m), which is the minimal and maximal requirement of the ith child.

Output

N integers which are the numbers of ways to distribute the m bones, one per line.

Sample Input

2
3 7
1 2
2 4
3 6
3 13
1 2
2 4
3 6

Sample Output

3
0

Submit

Source: WishingBone's Contest #1