물통

물통 A와 B는 가득 채우면 각각 $a$리터, $b$리터가 들어간다. 두 물통에는 눈금이 없어서, 비었거나 가득 찬 상태가 아니면 안에 물이 얼마나 있는지 알 수 없다. 처음에 A에는 $x$리터, B에는 $y$리터가 들어 있다. 옆에는 물이 무한히 있는 저수지가 있다.

눈금이 없으므로, 두 물통에 든 물의 양을 정확히 알면서 할 수 있는 작업은 다음 여섯 가지뿐이다.

• A 또는 B의 물을 저수지에 버린다.
• 저수지의 물로 A 또는 B를 가득 채운다.
• A가 빌 때까지 A의 물을 B로 옮긴다.
• B가 가득 찰 때까지 A의 물을 B로 옮긴다.
• B가 빌 때까지 B의 물을 A로 옮긴다.
• A가 가득 찰 때까지 B의 물을 A로 옮긴다.

정수 쌍 $O_i = (s_i, t_i)$를 목표량이라고 한다. A와 B가 각각 $s$리터, $t$리터를 담은 상태에서 위 작업을 0번 이상 적용해 A와 B가 정확히 $s_i$리터, $t_i$리터를 담게 만들 수 있으면, 목표량 $O_i$는 $(s, t)$에서 도달 가능하다고 한다.

목표량 $O_1, O_2, \dots, O_n$이 주어진다. $i_1 < i_2 < \dots < i_l$인 부분수열 $O_{i_1}, O_{i_2}, \dots, O_{i_l}$ 중에서 각 목표량이 바로 앞 목표량에서 도달 가능한 가장 긴 것을 찾아라. 연속할 필요는 없어서, $n$이 충분히 크면 $O_1, O_4, O_6, O_8$도 부분수열이 된다. $O_{i_1}$의 앞 목표량은 처음 상태 $(x, y)$로 본다. 처음 상태에서 첫 번째 목표량을 만들고, 첫 번째 목표량에서 두 번째 목표량을 만드는 식으로 이어지는 가장 긴 부분수열의 길이 $l$을 구하는 문제이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 다섯 정수 $a$, $b$, $x$, $y$, $n$이 주어진다 ($1 \le a, b \le 10^9$, $0 \le x \le a$, $0 \le y \le b$, $1 \le n \le 200000$). $a$와 $b$는 A와 B의 용량, $x$와 $y$는 처음에 A와 B에 든 물의 양, $n$은 목표량의 개수이다. 이어지는 $n$개 줄에는 목표량이 두 정수 $s$와 $t$로 주어진다 ($0 \le s \le a$, $0 \le t \le b$). $s$는 A가 담아야 할 물의 양, $t$는 B가 담아야 할 물의 양이다.

각 테스트 케이스마다 한 줄씩, 위에서 정의한 가장 긴 부분수열의 길이를 출력한다. $(x, y)$에서 도달할 수 있는 목표량이 하나도 없으면 0을 출력한다.