def floor_sum(n, m, a, b)
  res = 0
  if a >= m
    res += (n - 1) * n * (a / m) / 2
    a %= m
  end
  if b >= m
    res += n * (b / m)
    b %= m
  end

  y_max = (a * n + b) / m
  x_max = y_max * m - b
  if y_max == 0
    return res
  else
    res += (n - (x_max + a - 1) / a) * y_max
    res += floor_sum(y_max, a, m, - x_max % a)
    return res
  end
end

t = $stdin.readline.to_i
t.times do
  n, m, a, b = $stdin.readline.chomp.split.map(&:to_i)
  puts floor_sum(n, m, a, b)
end