Let's say we live on the infinite plane. You own a quadratic field, with bottom-left corner and top-right corner at points \((0, 0)\) and \((a,a)\) respectively. From time to time, your field is destroyed by animals, what doesn't make you very happy.

Limak is a big and dreadful grizzly bear. He lives at the point \((bx, by)\).

Other animals live in herds. A herd is a group of animals described by five integers \(k, x0, y0, dx, dy\). There are k animals in a herd, numbered 0 through \(k-1\) for convenience. An animal i lives at the point \((x0 + i \cdot dx, y0 + i \cdot dy)\).

Each of \(k + 1\) animals (bear Limak and k animals from a herd) lives strictly outside your field. Also, none two of those animals live at the same point.

When bear Limak roars, all other animals get scared and run away from him. After hearing the roar from some direction, an animal runs in the opposite direction. An example is showed in the Explanation section below.

You are given T independent test cases, each describing one herd. For each test case, count how many animals from a herd will run through your field after hearing Limak. Animals which only touch the border must be counted too.

Input format

The first line contains four integers \(T, a, bx, by\) — the number of herds, the size of your field and coordinates of bear Limak, respectively.

Each of the next T lines contains five integers \(k, x0, y0, dx, dy\), describing one herd.

Output format

For each test case print one integer in a separate line — the number of animals that will at least touch your field, while running away from Limak.

Constraints

• \(1 \le T \le 5000\)
• \(1 \le a \le 10^9\)
• \(-10^9 \le bx, by, x0, y0, dx, dy \le 10^9\)
• \(2 \le k \le 10^9\)
• None two animals from one herd live at the same point.
• No other animal coincides with bear Limak.
• All animals live strictly outside your field. In other words, \(x < 0\) or \(x > a\) or \(y < 0\) or \(y > a\), where \(x, y\) are coordinates of any animal (including Limak).