import scala.annotation.tailrec
import scala.collection.mutable
import scala.collection.mutable.ArrayBuffer
import scala.io.StdIn._

object Main extends App {
  solve()
  @tailrec def solve(): Unit = {
    val s = readLine.trim
    if (s == "#") return
    val q = readLine.trim
    s match {
      case Genome(g) ⇒ println(g.countPattern(q))
      case _ ⇒ ???
    }
    solve()
  }

  trait Genome {
    def countPattern(pattern: String): Long = {
      val automaton = Automaton(pattern)
      val defaultNext = ('A' to 'Z').map{c ⇒ automaton.map{_.move(c).id}}.toArray
      val defaultCount = Array.tabulate(26){c ⇒ Array.tabulate(automaton.length){i ⇒ if (defaultNext(c)(i) == pattern.length) 1L else 0L}}
      val matcher = makeMatcher(defaultNext, defaultCount)
      matcher.matchCount
    }
    protected def makeMatcher(defaultNext: Array[Array[Int]], defaultCount: Array[Array[Long]]): PatternMatcher
  }
  object Genome {
    def unapply(arg: String): Option[Genome] = {
      arg.toList match {
        case g SeqGenome Nil ⇒ Some(g)
        case _ ⇒ None
      }
    }
    private object SingleGenome {
      def unapply(arg: List[Char]): Option[(SingleGenome, List[Char])] = {
        arg match {
          case h::t if h.isUpper ⇒ Some(new SingleGenome(h), t)
          case _ ⇒ None
        }
      }
    }
    private class SingleGenome(char: Char) extends Genome {
      override protected def makeMatcher(defaultNext: Array[Array[Int]], defaultCount: Array[Array[Long]]): PatternMatcher = {
        new PatternMatcher(defaultNext(char - 'A'), defaultCount(char - 'A'))
      }
    }
    private object SeqGenome {
      def unapply(arg: List[Char]): Option[(SeqGenome, List[Char])] = {
        arg match {
          case g SingleGenome t ⇒ Some(takeAll(t, List(g)))
          case g RepeatGenome t ⇒ Some(takeAll(t, List(g)))
          case _ ⇒ None
        }
      }
      @tailrec private[this] def takeAll(arg: List[Char], genomes: List[Genome]): (SeqGenome, List[Char]) = {
        arg match {
          case g SingleGenome t ⇒ takeAll(t, g::genomes)
          case g RepeatGenome t ⇒ takeAll(t, g::genomes)
          case _ ⇒ (new SeqGenome(genomes.reverse), arg)
        }
      }
    }
    private class SeqGenome(genoms: List[Genome]) extends Genome {
      override protected def makeMatcher(defaultNext: Array[Array[Int]], defaultCount: Array[Array[Long]]): PatternMatcher = {
        genoms.map{_.makeMatcher(defaultNext, defaultCount)}.reduce(_ + _)
      }
    }
    private object RepeatGenome {
      def unapply(arg: List[Char]): Option[(RepeatGenome, List[Char])] = {
        arg match {
          case n Number '('::(g SeqGenome ')'::t) ⇒ Some(new RepeatGenome(g, n), t)
          case n Number (g SingleGenome t) ⇒ Some(new RepeatGenome(g, n), t)
          case _ ⇒ None
        }
      }
    }
    private class RepeatGenome(genome: Genome, times: Long) extends Genome {
      override protected def makeMatcher(defaultNext: Array[Array[Int]], defaultCount: Array[Array[Long]]): PatternMatcher = genome.makeMatcher(defaultNext, defaultCount).repeat(times)
    }
    private object Number {
      def unapply(arg: List[Char]): Option[(Long, List[Char])] = {
        arg.span(_.isDigit) match {
          case (Nil, _) ⇒ None
          case (n, t) ⇒ Some(n.foldLeft(0L){case (acc, c) ⇒ acc * 10 + c.asDigit}, t)
        }
      }
    }
  }

  class PatternMatcher(val next: Array[Int], val count: Array[Long]) {
    def matchCount: Long = count.head
    def +(that: PatternMatcher): PatternMatcher = {
      val newNext = Array.tabulate(next.length){i ⇒ that.next(next(i))}
      val newCount = Array.tabulate(count.length){i ⇒ count(i) + that.count(next(i))}
      new PatternMatcher(newNext, newCount)
    }
    def repeat(times: Long): PatternMatcher = {
      times match {
        case 1L ⇒ this
        case _ if times % 2 == 0 ⇒ (this + this).repeat(times / 2)
        case _ ⇒ (this + this).repeat(times / 2) + this
      }
    }
  }
  trait Automaton {
    def move(char: Char): Automaton
    def id: Int
    def isMatch: Boolean
  }
  object Automaton {
    def apply(word: String): Array[Automaton] = {
      val result = ArrayBuffer[AutomatonImpl](new RootImpl)
      for ((c, i) ← word.zipWithIndex) {
        result.append(new ChildImpl(result.last.move(c), i + 1, i == word.length - 1))
        result(i).nextStates += c → result.last
      }
      result.toArray
    }
    private trait AutomatonImpl extends Automaton {
      val nextStates: mutable.Map[Char, Automaton]
    }
    private class RootImpl extends AutomatonImpl {
      override val nextStates = mutable.Map[Char, Automaton]()
      override def move(char: Char): Automaton = nextStates.getOrElseUpdate(char, this)
      override def id: Int = 0
      override def isMatch: Boolean = false
    }
    private class ChildImpl(failure: Automaton, override val id: Int, override val isMatch: Boolean) extends AutomatonImpl {
      override val nextStates = mutable.Map[Char, Automaton]()
      override def move(char: Char): Automaton = nextStates.getOrElseUpdate(char, failure.move(char))
    }
  }
}


Measured memory_bytes: 684680