이 문제에는 첨부 파일이 있습니다. 이를 사용하여 입자의 움직임을 시뮬레이션하고 시각화할 수 있습니다.

VegiCat은 $n$개의 행과 $n$개의 열로 이루어진 격자 위의 입자들을 관찰합니다. 왼쪽 아래 칸의 좌표는 $(1, 1)$입니다. 수평 좌표는 왼쪽에서 오른쪽으로 증가하고, 수직 좌표는 아래에서 위로 증가합니다. 각 입자는 수평 방향(왼쪽 또는 오른쪽)과 수직 방향(위 또는 아래)을 가집니다. 각 단계가 시작될 때, 각 입자는 자신의 방향을 다음과 같이 조정합니다:

• 수평 방향으로 다음 칸이 격자 밖에 있다면 수평 방향이 반대로 바뀝니다.
• 수직 방향으로 다음 칸이 격자 밖에 있다면 수직 방향이 반대로 바뀝니다.

이러한 조정이 끝난 후, $(x, y)$에 있는 입자는 두 개의 자식 입자를 생성합니다:

• 수평 방향이 왼쪽이면 $(x - 1, y)$에, 오른쪽이면 $(x + 1, y)$에 하나;
• 수직 방향이 아래쪽이면 $(x, y - 1)$에, 위쪽이면 $(x, y + 1)$에 하나.

두 자식 입자는 모두 부모의 수평 및 수직 방향을 그대로 물려받습니다. 그런 다음 부모 입자는 사라집니다.

방향에 관계없이 여러 입자가 동시에 같은 칸을 차지할 수 있습니다. 입자들은 서로 상호작용하거나 서로의 방향을 바꾸지 않습니다.

시간 $0$일 때, $(x_0, y_0)$에 다음과 같은 방향 쌍을 가진 네 개의 입자가 있습니다:

• 오른쪽 및 위쪽;
• 왼쪽 및 위쪽;
• 오른쪽 및 아래쪽;
• 왼쪽 및 아래쪽.

각 단계마다 모든 입자는 동시에 방향을 조정한 뒤 위에서 설명한 대로 분열합니다.

$q$개의 쿼리가 주어집니다. 각 쿼리는 정수 $A, B, C$와 시간 $t$를 제공합니다. 각 쿼리에 대해, $Ax + By + C = 0$을 만족하면서 시간 $t$일 때 적어도 하나의 입자를 포함하는 격자 칸 $(x, y)$의 개수를 구하세요.

입력

첫째 줄에 테스트 케이스의 개수를 나타내는 정수 $T$ ($1 \le T \le 10^5$)가 주어집니다. 이어서 테스트 케이스의 설명이 주어집니다.

각 테스트 케이스의 첫째 줄에는 네 정수 $n, x_0, y_0, q$ ($2 \le n \le 10^9$, $1 \le x_0, y_0 \le n$, $1 \le q \le 10^5$)가 주어집니다. 격자는 $n$개의 행과 $n$개의 열로 이루어져 있으며, 초기 칸은 $(x_0, y_0)$이고 쿼리는 $q$개입니다.

다음 $q$개의 줄에는 각각 네 정수 $A, B, C$와 $t$ ($|A|, |B|, |C| \le 10^9$, $0 \le t \le 10^9$)가 주어집니다. 이는 시간 $t$일 때 직선 $Ax + By + C = 0$에 대한 쿼리를 나타냅니다. $A$와 $B$가 동시에 $0$이 아님이 보장됩니다.

모든 테스트 케이스에서 $q$의 합은 $10^5$을 초과하지 않음이 보장됩니다.

출력

각 쿼리마다 한 줄에 정수 하나를 출력합니다: 시간 $t$일 때 $Ax + By + C = 0$을 만족하고 적어도 하나의 입자를 포함하는 격자 칸 $(x, y)$의 개수입니다.

예제

예제 입력 1

1
6 5 5 4
2 -1 -5 0
1 -1 0 1
11 45 14 2
1 0 -5 3

예제 출력 1

1
0
0
3

참고

아래 그림은 예제에서의 입자 변화 과정과 쿼리로 주어진 직선들을 보여줍니다. 여기서 회색 칸은 직선이 지나는 정수 좌표를 포함하는 칸을 나타내며, 모든 분열 방향은 유효성 조정을 거친 상태입니다. 세 번째 쿼리는 고려 중인 격자에서 너무 멀리 떨어져 있으므로 세 번째 쿼리의 직선은 여기에서 생략되었습니다.

같은 칸에 있으면서 같은 방향 쌍을 가진 입자들은 하나의 기호로 그려졌으며, 중복도는 생략되었습니다.