You are given an arithmetic progression consisting of n elements, where the i-th element ai=(a+b⋅(i−1))modm.
Your task is to calculate the sum of the arithmetic progression ∑i=1nai given n, m, a and b.
The first line contains one integer t (1≤t≤105) — the number of test cases.
The next t lines contain four integers n, m, a and b each (1≤n≤109,2≤m≤109+7,0≤a,b<m) — description of arithmetic progression.
For each test example, print on a separate line a single number — the sum of the elements of the arithmetic progression.