NewCalendar.scala

import java.io.{FileInputStream, FileOutputStream}

import scala.io.StdIn

object calendar extends App{
  def gcd(a: Long,b: Long): Long = { if(b ==0) a else gcd(b, a%b) }

  Console.setIn(new FileInputStream("example.in"))
//  Console.setIn(new FileInputStream("A-large-practice.in"))
//  Console.setOut(new FileOutputStream("A-large-practice.out"))

  def solve(sets: String): Long = {
    val Array(month, day_month, day_week) = sets.split(" ").map(_.toLong)
    val nset = day_week / gcd(day_month, day_week)

    val lines = for(i <- 0L until nset) yield {
      val n = ((day_month % day_week) * i) % day_week + day_month

      if(n % day_week == 0) n / day_week else n / day_week + 1
    }
    (month/nset) * lines.sum + lines.take((month%nset).toInt).sum
  }
  val cases = StdIn.readLine().toInt
  (1 to cases) foreach { num =>
    val sets = StdIn.readLine()
    println(f"Case #$num: ${solve(sets)}")
  }
}