-- https://github.com/minoki/my-atcoder-solutions
{-# LANGUAGE TypeApplications #-}
{-# LANGUAGE BangPatterns #-}
import Data.Char (isSpace)
import Data.Int (Int64)
import Data.List (unfoldr)
import Control.Monad
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM
import qualified Data.ByteString.Char8 as BS
import Data.Ratio
import qualified Test.QuickCheck as QC

floorSum :: Int64 -> Int64 -> Int64 -> Int64 -> Int64
floorSum n m 0 b = n * floor (b % m)
floorSum 0 m a b = 0
floorSum n 1 a b = a * (n * (n - 1) `quot` 2) + n * b
floorSum n m a b | a >= m = case a `quotRem` m of
                              (q, a') -> q * (n * (n - 1) `quot` 2) + floorSum n m a' b
                 | b >= m || b < 0 = case b `divMod` m of
                                       (q, b') -> q * n + floorSum n m a b'
                 | n > m = case n `quotRem` m of
                             (q, n') -> (q * n - q * (q + 1) `quot` 2 * m) * a + q * floorSum m m a b + floorSum n' m a b
                 | n < 100 = fromInteger $ floorSum_naive n m a b
                 | otherwise = -- 0 < a < m, 0 <= b < m, 0 < n <= m
                     ceilSum (ceiling $ (a * (n - 1) + b) % m) a m (m - b)

ceilSum :: Int64 -> Int64 -> Int64 -> Int64 -> Int64
ceilSum n m 0 b = n * ceiling (b % m)
ceilSum 0 m a b = 0
ceilSum n 1 a b = a * (n * (n - 1) `quot` 2) + n * b
ceilSum n m a b | a >= m = case a `quotRem` m of
                              (q, a') -> q * (n * (n - 1) `quot` 2) + ceilSum n m a' b
                 | b >= m || b < 0 = case b `divMod` m of
                                       (q, b') -> q * n + ceilSum n m a b'
                 | n > m = case n `quotRem` m of
                             (q, n') -> (q * n - q * (q + 1) `quot` 2 * m) * a + q * ceilSum m m a b + ceilSum n' m a b
                 | n < 100 = fromInteger $ ceilSum_naive n m a b
                 | otherwise = n * (n - 1) `quot` 2 - floorSum n m (m - a) (- b) -- 0 < a < m, 0 <= b < m, 0 < n <= m

floorSum_naive :: Int64 -> Int64 -> Int64 -> Int64 -> Integer
floorSum_naive n m a b = sum [ floor ((fromIntegral a * fromIntegral i + fromIntegral b) % fromIntegral m) | i <- [0..n-1] ]

ceilSum_naive :: Int64 -> Int64 -> Int64 -> Int64 -> Integer
ceilSum_naive n m a b = sum [ ceiling ((fromIntegral a * fromIntegral i + fromIntegral b) % fromIntegral m) | i <- [0..n-1] ]

prop_floorSum :: QC.NonNegative (QC.Small Int64) -> QC.Positive Int64 -> Int64 -> Int64 -> QC.Property
prop_floorSum (QC.NonNegative (QC.Small n)) (QC.Positive m) a b = QC.within (100 * 1000) $ toInteger (floorSum n m a b) QC.=== floorSum_naive n m a b

prop_ceilSum :: QC.NonNegative (QC.Small Int64) -> QC.Positive Int64 -> Int64 -> Int64 -> QC.Property
prop_ceilSum (QC.NonNegative (QC.Small n)) (QC.Positive m) a b = QC.within (100 * 1000) $ toInteger (ceilSum n m a b) QC.=== ceilSum_naive n m a b

main = do
  t <- readLn @Int
  replicateM_ t $ do
    [n,m,a,b] <- map fromIntegral . unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
    print $ floorSum n m a b
