+ محدودیت زمان: 8 ثانیه + محدودیت حافظه: 1024 مگابایت ---------- شاید فکر کنید پوریا دست از سر شما برداشته است اما اشتباه می‌کنید! :) او که دیگر با شما صمیمی شده‌ است نه تنها سوال‌های خودش را به شما می‌دهد بلکه سوال‌های دوستش زهرا را نیز به شما می‌دهد تا حل کنید! او به شما اعداد $A$, $B$, $V$ و $M$ را می‌دهد به طوری که اعداد $A$ و $B$ همیشه نسبت به هم اول $(Coprime)$ یا همان متباین باشند. همچنین شما عدد $x$ را نیز دارید که در ابتدا $x=V$ است. شما می‌توانید یکی از چهار عملیات زیر را به هر تعدادی که می‌خواهید انجام دهید. + عوض کردن مقدار $x$ با $x + A$ + عوض کردن مقدار $x$ با $x - A$ + عوض کردن مقدار $x$ با $x + B$ + عوض کردن مقدار $x$ با $x - B$ این را بدانید که شرط $0 \le x \le M$ در مراحل عملیاتی که انجام می‌دهید باید رعایت شود. با توجه شرایط فوق چند مقدار مختلف برای $x$ وجود خواهد داشت؟ پوریا به زهرا قول داده که این سوال را برایش حل کند پس لطفا به او کمک کنید تا آبرویش پیش زهرا حفظ شود! # ورودی در خط اول عدد $T$ داده میشود که نشان دهنده تعداد ورودی‌هاست. در $T$ خط بعدی سه عدد $A$, $B$, $V$ و $M$ داده میشود ترتیب ورودی هر نمونه : ``` A B V M ``` # خروجی برای هر ورودی تعداد مقدارهای مختلف برای $x$ را چاپ کنید. # محدودیت ها $$1 \le T \le 10^5$$ $$1 \le A \le B \le M \le 10^9$$ $$0 \le V \le M$$ # مثال ## ورودی نمونه ۱ ``` 5 3 5 0 5 1 2 5 10 5 8 4 9 10 99 48 106 500000000 500000001 123456789 900000000 ``` ## خروجی نمونه ۱ ``` 4 11 4 10 800000002 ``` در ورودی اول مقدارهای مختلف و ممکن برای $x = 0, 2, 3, 5$ است