-- https://github.com/minoki/my-atcoder-solutions
{-# LANGUAGE TypeApplications #-}
import           Control.Monad
import qualified Data.ByteString.Char8 as BS
import           Data.Char             (isSpace)
import           Data.Int              (Int64)
import           Data.List             (unfoldr)
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
  | m < 0 = error "m must be positive"
  | a >= m || a < 0 = case a `divMod` 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
  | otherwise = -- 0 < a < m, 0 <= b < m, 0 < n <= m
      let t = floor ((toInteger a * (toInteger n - 1) + toInteger b) % toInteger m)
      in n * t + floorSum t a (- m) (b - 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] ]

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

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
