Soal ini memiliki lampiran. Anda dapat menggunakannya untuk menyimulasikan dan memvisualisasikan pergerakan partikel.

VegiCat mengamati partikel-partikel pada suatu kisi dengan $n$ baris dan $n$ kolom. Sel kiri bawah memiliki koordinat $(1, 1)$. Koordinat horizontal meningkat dari kiri ke kanan, dan koordinat vertikal meningkat dari bawah ke atas. Setiap partikel memiliki arah horizontal (kiri atau kanan) dan arah vertikal (atas atau bawah). Pada awal setiap langkah, setiap partikel menyesuaikan arahnya sebagai berikut:

• Arah horizontalnya dibalik jika sel berikutnya pada arah tersebut berada di luar kisi.
• Arah vertikalnya dibalik jika sel berikutnya pada arah tersebut berada di luar kisi.

Setelah penyesuaian ini, sebuah partikel di $(x, y)$ menghasilkan dua partikel anak:

• Satu di $(x - 1, y)$ jika arah horizontalnya ke kiri, atau di $(x + 1, y)$ jika ke kanan;
• Satu di $(x, y - 1)$ jika arah vertikalnya ke bawah, atau di $(x, y + 1)$ jika ke atas.

Kedua partikel anak mewarisi arah horizontal dan vertikal induknya. Partikel induk kemudian menghilang.

Beberapa partikel dapat menempati sel yang sama pada waktu yang sama, terlepas dari arahnya. Mereka tidak saling berinteraksi ataupun mengubah arah satu sama lain.

Pada waktu $0$, terdapat empat partikel di $(x_0, y_0)$, dengan pasangan arah berikut:

• Kanan dan atas;
• Kiri dan atas;
• Kanan dan bawah;
• Kiri dan bawah.

Pada setiap langkah, semua partikel secara bersamaan menyesuaikan arah mereka lalu membelah seperti yang dijelaskan di atas.

Anda diberikan $q$ kueri. Setiap kueri memberikan bilangan bulat $A, B, C$ dan waktu $t$. Untuk setiap kueri, carilah banyaknya sel kisi $(x, y)$ yang memenuhi $Ax + By + C = 0$ dan berisi setidaknya satu partikel pada waktu $t$.

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^5$), banyaknya kasus uji. Deskripsi dari masing-masing kasus uji menyusul di bawahnya.

Baris pertama dari setiap kasus uji berisi empat bilangan bulat $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$). Kisi memiliki $n$ baris dan $n$ kolom. Sel awal adalah $(x_0, y_0)$, dan terdapat $q$ kueri.

Masing-masing dari $q$ baris berikutnya berisi empat bilangan bulat $A, B, C$ dan $t$ ($|A|, |B|, |C| \le 10^9$, $0 \le t \le 10^9$). Ini mendeskripsikan sebuah kueri untuk garis $Ax + By + C = 0$ pada waktu $t$. Dijamin bahwa $A$ dan $B$ tidak keduanya bernilai $0$ secara bersamaan.

Dijamin bahwa jumlah $q$ di seluruh kasus uji tidak melebihi $10^5$.

Keluaran

Untuk setiap kueri, keluarkan satu bilangan bulat dalam satu baris: banyaknya sel kisi $(x, y)$ yang memenuhi $Ax + By + C = 0$ dan berisi setidaknya satu partikel pada waktu $t$.

Contoh

Masukan 1

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

Keluaran 1

1
0
0
3

Catatan

Gambar di bawah ini menunjukkan evolusi partikel pada contoh, beserta garis-garis lurus yang ditanyakan, di mana sel berwarna abu-abu menyatakan sel yang memuat titik bulat yang dilalui garis lurus tersebut, dan semua arah pembelahan telah menjalani penyesuaian keabsahan. Karena kueri ketiga berada terlalu jauh dari kisi yang ditinjau, garis untuk kueri ketiga dihilangkan di sini.

Partikel pada sel yang sama dengan pasangan arah yang sama digambarkan sebagai satu simbol tunggal; multiplisitasnya diabaikan.