Under construction

Still being built. Things may change

Faraway

Time limit1sMemory limit512 MB

Summary
Count lattice points (xe, ye) in [0, m]^2 such that for each of up to 10 constraints, (|xi - xe| + |yi - ye|) mod ki equals ti, with ki at most 5 and m up to 1e9.
Level

Hard9 of 10

Topics
Math, Number theory, Combinatorics, Implementation
Solved
No attempts yet

Problem

A squad of n soldiers is dispatched to somewhere in Byteland. Currently, the i-th soldier is at location (xi, yi). The soldiers are about to set off, but the target location is not clear.

Suppose the target location is (xe, ye). All soldiers know that xe and ye are both non-negative integers in the range [0, m]. Beyond that, the only thing the i-th soldier knows is that (|xi − xe| + |yi − ye|) mod ki = ti.

To find the correct target location, the soldiers work with the information they have. Write a program that determines the number of possible target locations.

Input

The first line of the input contains an integer T (1 ≤ T ≤ 10), the number of test cases.

Each test case starts with a line containing two integers n and m (1 ≤ n ≤ 10, 1 ≤ m ≤ 109), the number of soldiers and the upper bound for xe and ye.

Each of the next n lines contains four integers xi, yi, ki, and ti (0 ≤ xi, yi ≤ m, 2 ≤ ki ≤ 5, 0 ≤ ti < ki), the information the i-th soldier has.

Output

For each test case, print a single line containing a single integer: the number of possible target locations.

Examples1

  1. Example 1

    Input
    2
2 5
1 2 4 2
3 1 2 1
2 5
1 2 4 2
1 2 4 3
    Expected output
    10
0