#include <array>
#include <vector>
#include <future>
#include <limits>
#include <fstream>
#include <iostream>

using namespace std;

array<char, 26 * 26> lookup{};
int steps = 40;

using Frequencies = array<uint64_t, 26>;

void expand(char a, char b, int depth, Frequencies &freq)
{
    if (depth == steps) { ++freq[a]; return; }

    char toAdd = lookup[a*26 + b];
    expand(a, toAdd, depth + 1, freq);
    expand(toAdd, b, depth + 1, freq);
}

int main(int argc, const char** argv)
{
    if (argc > 1) steps = atoi(argv[1]);
    ifstream input("input14.txt");

    string prototype;
    input >> prototype;
    for (auto &c : prototype) c -= 'A';

    while (true)
    {
        string t1, t2, t3;
        input >> t1 >> t2 >> t3;
        if (t2 != "->") break;

        lookup[(t1[0] - 'A') * 26 + (t1[1] - 'A')] = t3[0] - 'A';
    }

    Frequencies freq{};

    vector<future<Frequencies>> jobs;
    for (size_t i = 0; i < prototype.size() - 1; ++i)
        jobs.push_back(async(std::launch::async, [a = prototype[i], b = prototype[i + 1]]
            {
                Frequencies f{};
                expand(a, b, 0, f);
                return f;
            }));

    for (auto &j : jobs)
    {
        auto f = j.get();
        for (size_t i = 0; i < f.size(); ++i) freq[i] += f[i];
    }

    // Don't forget the final character
    ++freq[prototype[prototype.size() - 1]];

    uint64_t biggest = 0;
    uint64_t smallest = numeric_limits<uint64_t>::max();
    for (auto &count : freq)
    {
        if (count == 0) continue;
        biggest = max(biggest, count);
        smallest = min(smallest, count);
    }

    cout << (biggest - smallest) << endl;
}