import qualified Control.Arrow         as Arrow
import qualified Data.ByteString.Char8 as BSC8
import qualified Data.Char             as Char
import qualified Data.Vector           as V
import qualified Data.Vector.Unboxed   as VU

type Parser a = BSC8.ByteString -> Maybe (a, BSC8.ByteString)
parseInt :: Parser Int
parseInt = fmap (Arrow.second BSC8.tail) . BSC8.readInt
parse1 :: IO Int
parse1 = readLn
parse4 :: IO (Int, Int, Int, Int)
parse4 = (\vec -> (vec VU.! 0, vec VU.! 1, vec VU.! 2, vec VU.! 3)) . VU.unfoldrN 4 parseInt <$> BSC8.getLine
parseNM :: Int -> Int -> IO (V.Vector (VU.Vector Int))
parseNM n m = V.replicateM n $ VU.unfoldrN m parseInt <$> BSC8.getLine

main :: IO ()
main = do
  t    <- parse1
  nmab <- parseNM t 4
  putStr . unlines . map show . V.toList $ V.map sumOfFloorLinear nmab

sumOfFloorLinear :: VU.Vector Int -> Int
sumOfFloorLinear nmab = iter n m a b 0
  where
    n = nmab VU.! 0
    m = nmab VU.! 1
    a = nmab VU.! 2
    b = nmab VU.! 3
    iter :: Int -> Int -> Int -> Int -> Int -> Int
    iter p q r s ret
      | r >= q && s >= q = if y1 == 0 then ret1' else ret1'' + iter y1 a1 q ((a1 - x1 `mod` a1) `mod` a1) 0
      | r >= q && s <  q = if y2 == 0 then ret2' else ret2'' + iter y2 a2 q ((a2 - x2 `mod` a2) `mod` a2) 0
      | r <  q && s >= q = if y3 == 0 then ret3' else ret3'' + iter y3 a3 q ((a3 - x3 `mod` a3) `mod` a3) 0
      | otherwise        = if y4 == 0 then ret4' else ret4'' + iter y4 a4 q ((a4 - x4 `mod` a4) `mod` a4) 0
      where
        ret1  = ret + (p - 1) * p * (r `div` q)
        a1    = r `mod` q
        ret1' = ret1 + p * (s `div` q)
        b1    = s `mod` q
        y1    = (a1 * p + b1) `div` q
        x1    = y1 * q - b1
        ret1'' = ret1' + (p - (x1 + a1 - 1) `div` a1) * y1
        
        ret2' = ret + (p - 1) * p * (r `div` q) `div` 2
        a2    = r `mod` q
        b2    = s
        y2    = (a2 * p + b2) `div` q
        x2    = y2 * q - b2
        ret2'' = ret2' + (p - (x2 + a2 - 1) `div` a2) * y2

        ret3' = ret + p * (s `div` q)
        a3    = r
        b3    = s `div` q
        y3    = (a3 * p + b3) `div` q
        x3    = y3 * q - b3
        ret3'' = ret3' + (p - (x3 + a3 - 1) `div` a3) * y3
        
        ret4' = ret
        a4    = r
        b4    = s
        y4    = (a4 * p + b4) `div` q
        x4    = y4 * q - b4
        ret4'' = ret4' + (p - (x4 + a4 - 1) `div` a4) * y4
