Haircut.scala

import java.io.{FileInputStream, FileOutputStream}

import scala.io.StdIn

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

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

  def solve(n: Int, times:List[Long]): Long = {
    def cutNum(t: Long):Long = times.map(x => (t + x - 1) / x).sum

    def findCutTime(minTime:Long, maxTime:Long):Long = {
      val testTime = (maxTime + minTime) / 2
      val c = cutNum(testTime)

      if (minTime + 1 == maxTime && c <= n) testTime
      else if (c > n) findCutTime(minTime, testTime)
      else findCutTime(testTime, maxTime)
    }
    val cutTime = findCutTime(0, times.max * n)
    times.zipWithIndex.filter(0 == cutTime % _._1)((n - cutNum(cutTime)).toInt)._2
  }

  val cases = StdIn.readLine().toInt
  (1 to cases) foreach { n =>
    val Array(b, ns) = StdIn.readLine().split(" ").map(_.toInt)
    val times = StdIn.readLine().split(" ").map(_.toLong).toList
    println(s"Case #$n: ${solve(ns - 1, times) + 1}")
  }
}