PartElf.scala

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

object Main {

  def gcd(p: BigInt, q: BigInt): BigInt = if (q == 0) p else gcd(q, p % q)

  def solve(p: BigInt, q: BigInt, r: Int = 0): String = q.bitCount == 1 match {
    case true => p >= q match {
      case true => r.toString
      case false => solve(p * 2, q, r + 1)
    }
    case false => "impossible"
  }


  def main(args: Array[String]) {
    val lines = Source.fromFile("sample.in").getLines()
    val w = new PrintWriter(new File("sample.out"))
    val caseNum = lines.next().toInt
    1 to caseNum foreach {
      caseIndex => {
        val Array(p, q) = lines.next().split("/").map(BigInt(_))
        val g = gcd(p, q)

        val answer = solve(p / g, q / g)
        println(s"Case #$caseIndex: $answer")

        w.println(s"Case #$caseIndex: $answer")
      }
    }
    w.flush();
  }
}