logging.scala

import java.io.{FileInputStream, FileOutputStream}

import scala.annotation.tailrec
import scala.io.StdIn

object Main extends App {
  Console.setIn(new FileInputStream("example.in"))

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


  def solve(trees:List[(Long, Long)]): List[Long] = {
    trees.map{case (x1, y1) =>
      @tailrec
      def traverse(ys:List[(Long,Long)], min:Long):Long = ys match {
        case List() => min
        case _ if min == 0 => 0
        case (x2, y2) :: xs if (x2, y2) == (x1, y1) => traverse(xs, min)
        case (x2, y2) :: xs => {

          val diffX: Long = x1 - x2
          val multipleX = y1 * diffX + (y1 - y2)

          def lineFx(t:(Long, Long)) = {
            if (x1 == x2) t._1 - x1
            else multipleX * (t._1 - x1) - t._2 * diffX
          }

          @tailrec
          def findMin(trees:List[(Long, Long)], yPlusAccr:Long = 0 , yMinusAccr:Long = 0):Long = trees match {
            case List() => yPlusAccr min yMinusAccr
            case x :: xs => {
             val y = lineFx(x)
              if (0 < y) findMin(xs, yPlusAccr + 1, yMinusAccr)
              else if (0 > y) findMin(xs, yPlusAccr, yMinusAccr + 1)
              else findMin(xs, yPlusAccr, yMinusAccr)
            }
          }
          traverse(xs, min min findMin(trees))
        }
      }
      traverse(trees, trees.length)
    }
  }

  val cases = StdIn.readLine().toInt
  (1 to cases) foreach { n =>
    val totalTrees = StdIn.readLine().toInt
    val trees = (1 to totalTrees) map {
      n => {
        val Array(x, y) = StdIn.readLine().split(" ").map(_.toLong)
        (x, y)
      }
    }
    println(s"Case #$n:\n${solve(trees.toList).mkString("\n")}")
  }
}