PartElf.scala

object PartElf extends App {

  def minGen(p: Long, q: Long): Option[Int] = {

    val Seq(a, b) = {
      @annotation.tailrec
      def gcd(a: Long, b: Long): Long = if (a == 0) b else gcd(b % a, a)

      val g = gcd(p, q)
      Seq(p, q).map(BigInt(_) / g)
    }

    if (b.bitCount > 1 || b.bitLength > 40) None
    else Some(b.bitLength - a.bitLength)

  }

  def process(iter: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to iter.next().toInt) {
      val Array(p, q) = iter.next().split('/').map(_.toLong)
      lineOut(s"Case #$i: ${minGen(p, q) getOrElse "impossible"}")
    }

  val writer = new java.io.PrintWriter("a.out")
  try {
    process(io.Source.fromFile("A-large-practice.in").getLines)(writer.println)
  } finally {
    writer.flush(); writer.close()
  }

}