import argparse
import functools
from typing import NamedTuple, List, Dict, Set, Tuple, Optional
from collections import Counter, defaultdict
import sys
from functools import lru_cache

parser = argparse.ArgumentParser()
parser.add_argument("ifile", type=argparse.FileType('r'))
args = parser.parse_args()

pair_rules: Dict[str, str] = dict()
template = args.ifile.readline().strip()
args.ifile.readline()  # skip blank line

for line in args.ifile.readlines():
    chunks = line.strip().split(" ")
    pair_rules[chunks[0]] = chunks[2]


def polymerize(template: str):
    global pair_rules
    constructed = "" + template[0]
    prev = template[0]
    for index in range(1, len(template)):
        constructed += pair_rules.get(prev + template[index], "")
        prev = template[index]
        constructed += template[index]
    return constructed


@lru_cache(2048)
def polyCount(template: str, steps: int):
    polymer = polymerize(template)

    if steps == 1:
        return Counter(polymer)

    stuff = [polyCount(polymer[index] + polymer[index + 1], steps - 1) for index in range(0, len(polymer) - 1)]
    return functools.reduce(lambda acc, val: acc + val, stuff) - Counter(polymer[1:-1])

counts = polyCount(template, 40).most_common()
print(counts[0][1] - counts[-1][1])