Today Mary's math homework is to solve an equation.

She knows all k_i and p_i, and 1 ≤ x_i ≤ M. All x_i must be integers. She must work out the number of different solutions of this equation this day. Can you give her a hand?

Input

There is a single integer T in the very first line of the input denoted the number of tests. T blocks follow.

For each test case:

The first line contains a single integer n (n ≤ 6). The second line contains a single integer m (m ≤ 150). n lines follow, each contains two space-separated integers k_i and p_i, i = 1, 2 ... n. All p_i are positive.

Output

For each test case output a single line, which contains a single integer - the answer. You may assume this number is less than 2³¹.

Example

Input:
1
3
150
1 2
-1 2
1 2
Output:
178

Warning: The time limit is very strict for this problem.