تحتوي هذه المسألة على مرفق. يمكنك استخدامه لمحاكاة وتصور حركة الجسيمات.

يراقب 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$. لكل استعلام، أوجد عدد خلايا الشبكة $(x, y)$ التي تحقق $Ax + By + C = 0$ وتحتوي على جسيم واحد على الأقل عند الزمن $t$.

الإدخال

يحتوي السطر الأول على عدد صحيح $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$). يصف هذا استعلاماً للمستقيم $Ax + By + C = 0$ عند الزمن $t$. من المضمون أن $A$ و $B$ لا يساويان $0$ معاً في الوقت نفسه.

من المضمون أن مجموع $q$ عبر جميع حالات الاختبار لا يتجاوز $10^5$.

الإخراج

لكل استعلام، اطبع عدداً صحيحاً واحداً في سطر مستقل: عدد خلايا الشبكة $(x, y)$ التي تحقق $Ax + By + C = 0$ وتحتوي على جسيم واحد على الأقل عند الزمن $t$.

أمثلة

الإدخال 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

ملاحظة

يوضح الشكل أدناه تطور الجسيمات في المثال بالإضافة إلى المستقيمات المستعلم عنها، حيث تمثل الخلايا الرمادية الخلايا التي تحتوي على نقاط ذات إحداثيات صحيحة يمر بها المستقيم، وقد خضعت جميع اتجاهات الانقسام لتعديلات الصلاحية. ونظراً لأن الاستعلام الثالث بعيد جداً عن الشبكة قيد الدراسة، فقد حُذف مستقيم الاستعلام الثالث هنا.

تُرسم الجسيمات الموجودة في الخلية نفسها والتي لها زوج الاتجاهات نفسه كرمز واحد؛ وتُحذف التكرارات.