Arithmetic progression

You are given an arithmetic progression consisting of $n$ elements, where the $i$-th element $a_i=(a+b\cdot (i-1))\mathrm{mod}m$.

Your task is to calculate the sum of the arithmetic progression ${\sum }_{i=1}^n{a}_i$ given $n$, $m$, $a$ and $b$.

Input

The first line contains one integer $t(1\le t\le 10^5)$ — the number of test cases.

The next $t$ lines contain four integers $n$, $m$, $a$ and $b$ each $(1\le n\le 10^9,2\le m\le 10^9+7,0\le a,b<m)$ — description of arithmetic progression.

Output

For each test example, print on a separate line a single number — the sum of the elements of the arithmetic progression.

Examples