Арифметична прогресія

Вам задано арифметичну прогресію, що складається з $n$ елементів, де $i$-й елемент визначається як $a_i=(a+b\cdot (i-1))\mathrm{mod}m$.

Ваше завдання — обчислити суму цієї арифметичної прогресії ${\sum }_{i=1}^n{a}_i$ для заданих значень $n$, $m$, $a$ і $b$.

Вхідні дані

Перший рядок містить одне ціле число $t(1\le t\le 10^5)$, яке вказує на кількість тестових прикладів.

У наступних $t$ рядках наведено по чотири цілі числа $n$, $m$, $a$ і $b(1\le n\le 10^9,2\le m\le 10^9+7,0\le a,b<m)$, що описують арифметичну прогресію.

Вихідні дані

Для кожного тестового прикладу виведіть одне число в окремому рядку — суму елементів арифметичної прогресії.

Приклади