## Problem Description

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

## Source

WishingBone