GoogolString.scala

object GoogolString {
  def findN(k:Long, n:Long=0):Long = if (0 == k) n else findN(k / 2, n + 1)
  def total(k: Long): Long = (1L << findN(k)) - 1

  def solve(k:Long):Int = {
    if (k == 1) 0
    else if (k == total(k) / 2 + 1) 0
    else 1 - solve(total(k) - k + 1)
  }

  def process(lineIn: Iterator[String])(lineOut: String => Unit) =
    for (i <- 1 to lineIn.next.toInt) {
      val n = lineIn.next.toLong

      lineOut(s"Case #$i: ${solve(n)}")
    }

  def main(args: Array[String]) = {
    val writer = new java.io.PrintWriter("a.out")
    try {
      //process(io.Source.fromFile("E-small-practice.in").getLines)(writer.println)
      process(io.Source.fromFile("googol-string/A-large-practice.in").getLines)(writer.println)
//      process(io.Source.fromFile("googol-string/sample.in").getLines)(println)
    } finally {
      writer.flush(); writer.close()
    }
  }
}