nn soldiers are dispatched to somewhere in Byteland. These soldiers are going to set off now, but the target location is not so clear.
Assume the target location is at (xe,ye)(xe,ye), it is clear that xe,yexe,ye are both non-negative integers within [0,m][0,m]. For the ii-th soldier, the only thing he knows is that (|xi−xe|+|yi−ye|)modki=ti(|xi−xe|+|yi−ye|)modki=ti.
To find the correct target location, these soldiers are working on the information they have now. Please write a program to figure out the number of possible target locations.
Input
The first line of the input contains an integer T(1≤T≤10)T(1≤T≤10), denoting the number of test cases.
In each test case, there are two integers n,m(1≤n≤10,1≤m≤109)n,m(1≤n≤10,1≤m≤109) in the first line, denoting the number of soldiers and the upper bound of xe,yexe,ye.
For the next nn lines, each line contains four integers xi,yi,ki,ti(0≤xi,yi≤m,2≤ki≤5,0≤ti<ki)xi,yi,ki,ti(0≤xi,yi≤m,2≤ki≤5,0≤ti<ki), denoting what each soldier knows.
Output
For each test case, print a single line containing an integer, denoting the number of possible target locations.