import scala.annotation.tailrec

object Main extends App {

  import scala.io.StdIn._
  import scala.io.Source
  var target = readLine.trim
  while (target != "0"){
    println(solve(target, readLine.trim))
    target = readLine.trim
  }
  def solve(target: String, expression: String): Long = {
    val t = target.toInt
    val exp = expression.toList.map {
      case '+' ⇒ OperatorPlus
      case '*' ⇒ OperatorMultiple
      case '(' ⇒ StartPer
      case ')' ⇒ EndPer
      case c if c.isDigit ⇒ Number(c.toString.toLong)
      case _ ⇒ throw new Exception
    }
    search(exp, new E(), t, 0).count
  }
  sealed trait Token
  object OperatorPlus extends Token
  object OperatorMultiple extends Token
  object StartPer extends Token
  object EndPer extends Token
  case class Number(value: Long) extends Token
  @tailrec def search(expression: List[Token], prev: E, target: Long, currentCount: Long, overflowed: Boolean = false):Result = {
    expression match{
      case Nil ⇒ Result(expression, currentCount, if (overflowed) target + 1 else prev.value, overflowed)
      case StartPer::t ⇒ {
        val innerResult = searchInner(t, new E(), target)
        if (innerResult.isOverflowed)
          search(innerResult.rest, new E(), target, innerResult.count + currentCount, true)
        else
          search(Number(innerResult.wholeValue)::innerResult.rest, prev, target, innerResult.count + currentCount, overflowed)
      }
      case EndPer::t ⇒ Result(t, currentCount, if (overflowed) target + 1 else prev.value, overflowed)
      case op::StartPer::t ⇒ {
        val innerResult = searchInner(t, new E(), target)
        if (innerResult.isOverflowed) search(innerResult.rest, new E(), target, innerResult.count + currentCount, true)
        else search(op::Number(innerResult.wholeValue)::innerResult.rest, prev, target, innerResult.count + currentCount, overflowed)
      }
      case OperatorMultiple::Number(num)::t ⇒ {
        var queue = prev.enqueueTimes(num)
        val isOverflowed = queue.value > target
        while (queue.value > target){
          queue = queue.dequeue
        }
        search(t, queue, target, currentCount + (if (queue.value == target) queue.leftValueLength else 0), isOverflowed || overflowed)
      }
      case OperatorPlus::Number(num)::t ⇒ {
        var queue = prev.enqueuePlus(num)
        val isOverflowed = queue.value > target
        while (queue.value > target){
          queue = queue.dequeue
        }
        search(t, queue, target, currentCount + (if (queue.value == target) queue.leftValueLength else 0), isOverflowed || overflowed)
      }
      case Number(num)::t ⇒ search(t, new E(num), target, currentCount + (if (num == target) 1 else 0), (num > target) || overflowed)
      case _ ⇒ {
        throw new Exception
      }
    }
  }
  def searchInner(expression: List[Token], prev: E, target: Long): Result = {
    search(expression, prev, target, 0, false)
  }
  case class Result(rest: List[Token], count: Long, wholeValue:Long, isOverflowed: Boolean)
  sealed trait PartialExpression{
    def value: Long
  }

  class Multiple private(private val queue: ImmutableQueue[Long], override val value: Long, private val oneLength: ImmutableQueue[Int], private val tailOneLength: Int, private val count:Int) extends PartialExpression {
    def this(value: Long) = this(ImmutableQueue().enqueue(value), value, ImmutableQueue(),if (value == 1) 1 else 0, 1)
    def this() = this(ImmutableQueue(), 0, ImmutableQueue(), 0, 0)
    def isEmpty: Boolean = queue.isEmpty
    def dequeue: Multiple = {
      if (queue.isEmpty) throw new Exception
      if (queue.front == 1){
        if (oneLength.isEmpty) {
          if (tailOneLength == 1) new Multiple(queue.dequeue, if (count == 1) 0 else value, oneLength, 0, count - 1)
          else new Multiple(queue, value, oneLength, tailOneLength - 1, count - 1)
        } else {
          val length = oneLength.front
          val popped = oneLength.dequeue
          if (length == 1) new Multiple(queue.dequeue, value, popped, tailOneLength, count - 1)
          else new Multiple(queue, value, popped.pushFront(length - 1), tailOneLength, count - 1)
        }
      }else {
        new Multiple(queue.dequeue, if (count == 1) 0 else value / queue.front, oneLength, tailOneLength, count - 1)
      }
    }
    def enqueue(num: Long): Multiple = {
      if (queue.isEmpty) new Multiple(num)
      else {
        if (num == 1) {
          if (tailOneLength == 0) new Multiple(queue.enqueue(1), value, oneLength, 1, count + 1)
          else new Multiple(queue, value, oneLength, tailOneLength + 1, count + 1)
        }else {
          if (tailOneLength == 0) new Multiple(queue.enqueue(num), value * num, oneLength, 0, count + 1)
          else new Multiple(queue.enqueue(num), value * num, oneLength.enqueue(tailOneLength), 0, count + 1)
        }
      }
    }
    def leftValueLength: Int = {
      if (queue.isEmpty) throw new Exception
      else if (queue.front != 1) 1
      else if (oneLength.isEmpty) tailOneLength + (if (tailOneLength == count) 0 else 1)
      else oneLength.front + (if (oneLength.front == count) 0 else 1)
    }
  }
  object E{
    private class ClosedE(private val queue: ImmutableQueue[Multiple], val value: Long) {
      def this() = {
        this(ImmutableQueue(), 0)
      }
      def dequeue: ClosedE = {
        if (queue.isEmpty) throw new Exception
        val front = queue.front
        val popped = queue.dequeue
        val frontPopped = front.dequeue
        if (frontPopped.isEmpty) new ClosedE(popped, value - front.value)
        else new ClosedE(popped.pushFront(frontPopped), value - front.value + frontPopped.value)
      }
      def enqueue(multiple: Multiple): ClosedE = {
        new ClosedE(queue.enqueue(multiple), this.value + multiple.value)
      }
      def isEmpty: Boolean = queue.isEmpty
      def leftValueLength: Int = {
        if (this.isEmpty) throw new Exception
        queue.front.leftValueLength
      }
    }
  }
  class E private (private val queue: E.ClosedE, override val value: Long, private val last: Multiple) extends PartialExpression {
    def this() {
      this(new E.ClosedE, 0, new Multiple())
    }
    def this(value: Long) {
      this(new E.ClosedE, value, new Multiple(value))
    }
    def dequeue: E = {
      if (queue.isEmpty) {
        val popped = last.dequeue
        new E(queue, popped.value, popped)
      }else {
        val popped = queue.dequeue
        new E(popped, popped.value + last.value, last)
      }
    }
    def enqueuePlus(num: Long): E = {
      if (last.isEmpty) new E(queue, num, last.enqueue(num))
      else new E(queue.enqueue(last), this.value + num, new Multiple(num))
    }
    def enqueueTimes(num: Long): E = {
      val pushed = last.enqueue(num)
      new E(queue, this.value - last.value + pushed.value, pushed)
    }
    def leftValueLength: Int = {
      if (queue.isEmpty) last.leftValueLength
      else queue.leftValueLength
    }

  }
  object ImmutableQueue{
    def apply[T](): ImmutableQueue[T] = new ImmutableQueue()
  }
  class ImmutableQueue[+T] private(private val reversed: List[T], private val enqueued: List[T]) {
    //Queueが空でない限りreversedはNilではない
    def this(){this(Nil, Nil)}
    def isEmpty:Boolean = reversed match{
      case Nil ⇒ true
      case _ ⇒ false
    }
    def isNotEmpty:Boolean = !isEmpty
    def enqueue[A >: T](value: A): ImmutableQueue[A] = {
      reversed match{
        case Nil ⇒ new ImmutableQueue((value::enqueued).reverse, Nil)
        case _ ⇒ new ImmutableQueue(reversed, value::enqueued)
      }
    }
    def pushFront[A >: T](value: A): ImmutableQueue[A] = new ImmutableQueue(value::reversed, enqueued)
    def pushBack[A >: T](value: A): ImmutableQueue[A] = enqueue(value)
    def dequeue: ImmutableQueue[T] = {
      reversed match{
        case Nil ⇒ throw new Exception
        case _::Nil ⇒ new ImmutableQueue(enqueued.reverse, Nil)
        case _::t ⇒ new ImmutableQueue(t, enqueued)
      }
    }
    def front: T = {
      reversed match{
        case Nil ⇒ throw new Exception
        case h::_ ⇒ h
      }
    }
  }
}


Measured memory_bytes: 817036