Buckets

Buckets A and B hold $a$ and $b$ liters of water when full. Neither bucket has measuring lines, so you cannot tell how much water is inside unless the bucket is empty or full. Bucket A starts with $x$ liters and bucket B starts with $y$ liters. Next to them is a reservoir that holds an unlimited amount of water.

Because the buckets have no measuring lines, keeping the exact contents of both buckets known leaves you only these six operations.

• Empty A or B into the reservoir.
• Fill A or B from the reservoir.
• Move water from A to B until A is empty.
• Move water from A to B until B is full.
• Move water from B to A until B is empty.
• Move water from B to A until A is full.

A pair of integers $O_i = (s_i, t_i)$ is called a target amount. The target amount $O_i$ is achievable from $(s, t)$ if some sequence of zero or more of the operations above turns buckets holding exactly $s$ and $t$ liters into buckets holding exactly $s_i$ and $t_i$ liters.

You are given target amounts $O_1, O_2, \dots, O_n$. Find the longest subsequence $O_{i_1}, O_{i_2}, \dots, O_{i_l}$ with $i_1 < i_2 < \dots < i_l$ such that each one is achievable from the previous one. The subsequence does not have to be consecutive, so $O_1, O_4, O_6, O_8$ is allowed when $n$ is large enough, and the previous one for $O_{i_1}$ is the starting pair $(x, y)$. In other words, you make the first target amount from the starting pair using only the operations above, then the second from the first, and so on. Print the length $l$ of the longest such subsequence.

The first line has the number of test cases $T$. Each test case starts with a line of five integers $a$, $b$, $x$, $y$, and $n$ ($1 \le a, b \le 10^9$, $0 \le x \le a$, $0 \le y \le b$, $1 \le n \le 200000$), where $a$ and $b$ are the capacities of A and B, $x$ and $y$ are the starting amounts of water in A and B, and $n$ is the number of target amounts. Each of the next $n$ lines has a target amount as two integers $s$ and $t$ ($0 \le s \le a$, $0 \le t \le b$), the amount of water to be held in A and in B.

Print exactly one line for each test case. The line holds the length of the longest subsequence defined above. Print 0 when no target amount is achievable from $(x, y)$.