PartElf.scala

import scala.io.Source
import java.io.PrintWriter
import java.io.File

object PartElf {

  val in = Source.fromFile("small.in").getLines
  val printer = new PrintWriter(new File("small.out"))

  case class TestCase(line: String) {

    val Array(_numor, _denom) = line.split("/").map(_.toInt)
    val factor = gcd(_numor, _denom)
    def gcd(a: Int, b: Int): Int = {
      if (b == 0) a else gcd(b, a % b)
    }

    val numor = _numor / factor
    val denom = _denom / factor

    def solve: String = {
      if (BigInt(denom).bitCount != 1) "impossible"
      else process.toString
    }

    def process: Int = {
      denom.toBinaryString.reverse.indexOf('1') - numor.toBinaryString.reverse.indexOf('1')
    }
  }

  def main(args: Array[String]) {
    val nOfCases: Int = in.next.toInt
    for {
      i <- 1 to nOfCases
    } {
      // Case #1: 1
      val tc = TestCase(in.next.toString())
      val out = s"Case #$i: ${tc.solve}"
      println(out)
      printer.println(out)
    }
    printer.flush()
  }
}