לבעיה זו מצורף קובץ. ניתן להשתמש בו כדי לדמות ולהמחיש חזותית את תנועות החלקיקים.

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

הערה

האיור שלהלן מציג את התפתחות החלקיקים בדוגמה וכן את הישרים שנשאלו, כאשר התאים האפורים מייצגים את התאים המכילים נקודות שלמות שדרכן עובר הישר, וכל כיווני הפיצול עברו התאמות חוקיות. מאחר שהשאילתה השלישית רחוקה מדי מהרשת הנדונה, הישר של השאילתה השלישית הושמט כאן.

חלקיקים באותו תא עם אותו זוג כיוונים מצוירים כסמל יחיד; הריבוי הושמט.