BLUEEQ2 - Help Blue Mary Please! (Act II)

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

She knows all ki and pi, and 1<=xi<=M. All xi 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 ki and pi, i=1,2,...,n. All pi 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^31.

Example

Input:
1
3
150
1 2
-1 2
1 2

Output:
178

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


Added by:Fudan University Problem Setters
Date:2007-04-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL GOSU JS-RHINO
Resource:Chinese National Olympiad in Informatics 2001,Day 2; translated by Blue Mary

hide comments
2016-08-20 14:30:01
p is not larger than 31 :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.