TwoTwo.scala

import scala.collection.mutable.{ Map => MMap }

object Solution {
  case class PrefixTrieNode(
      base: Char, // current node
      next: MMap[Char, PrefixTrieNode]) {
    var v: Boolean = false
  }

  class PrefixTrieTree {
    val root: PrefixTrieNode = PrefixTrieNode(
      '\u0000',
      MMap[Char, PrefixTrieNode]())

    val insertMonitor = new AnyRef

    def put(k: String) = {
      var p = root
      for (c <- k) {
        insertMonitor.synchronized {
          if (!p.next.contains(c)) {
            p.next += (c -> PrefixTrieNode(c, MMap[Char, PrefixTrieNode]()))
          }
        }
        p = p.next.get(c).get
      }
      p.v = true
    }

    def next(c: Char, n: PrefixTrieNode): Option[PrefixTrieNode] = n.next.get(c)

    def next(c: Char): Option[PrefixTrieNode] = root.next.get(c)

    def count(s: String) = {
      s.toCharArray.foldLeft((0, Array[PrefixTrieNode]().par)) { (l, c) =>
        val n = l._2.flatMap { p =>
          next(c, p)
        }
        next(c) match {
          case Some(v) =>
            if (v.v) {
              (l._1 + n.count(_.v) + 1, n :+ v)
            } else {
              (l._1 + n.count(_.v), n :+ v)
            }
          case None =>
            (l._1 + n.count(_.v), n)
        }
      }._1
    }
  }

  def main(args: Array[String]) {
    val bi1 = scala.math.BigInt.long2bigInt(1)
    val r = new PrefixTrieTree()
    r.put("1".toString);
    (0 to 800).par.foldLeft(bi1) { (l, c) => val v = l * 2; r.put(v.toString); v }
    (1 to Console.in.readLine().toInt).map { i =>
      (Console.in.readLine(), i)
    }.par.map { e =>
      (e._2, r.count(e._1))
    }.toArray.sortWith(_._1 < _._1).map(_._2).foreach { v =>
      println(v)
    }

  }
}