const AutoHashMap = std.AutoHashMap;
const FixedBufferAllocator = std.heap.FixedBufferAllocator;
const math = std.math;
const print = std.debug.print;
const split = std.mem.split;
const std = @import("std");
const tokenize = std.mem.tokenize;

const Children = packed struct { left: Pair, right: Pair };
const Pair = packed struct { left: u8, right: u8 };
const Rule = packed struct { adj: Pair, _: u32, ins: u8 };

fn KV(comptime M: type, comptime index: usize) type {
    const type_info = @typeInfo(@typeInfo(M).Pointer.child.KV);
    return type_info.Struct.fields[index].field_type;
}

fn addOrPut(map: anytype, key: KV(@TypeOf(map), 0),
            value: KV(@TypeOf(map), 1)) !void {
    const result = try map.getOrPut(key);
    if (result.found_existing)
        result.value_ptr.* += value
    else
        result.value_ptr.* = value;
}

pub fn main() !void {
    var buffer: [0xdecaf]u8 = undefined;
    var fba = FixedBufferAllocator.init(buffer[0..]);
    var input = split(@embedFile("input"), "\n\n");
    var count = AutoHashMap(Pair, usize).init(&fba.allocator);
    defer count.deinit();
    const template = input.next().?;
    for (template[0..template.len-1]) |*c|
        try addOrPut(&count, @ptrCast(*const Pair, c).*, 1);

    var rules = tokenize(input.next().?, "\n");
    var insertions = AutoHashMap(Pair, Children).init(&fba.allocator);
    defer insertions.deinit();
    while (rules.next()) |rule| {
        const unmasked = @ptrCast(*const Rule, rule.ptr);
        try insertions.put(unmasked.adj, .{
            .left = .{ .left = unmasked.adj.left, .right = unmasked.ins },
            .right = .{ .left = unmasked.ins, .right = unmasked.adj.right },
        });
    }

    var result = AutoHashMap(u8, usize).init(&fba.allocator);
    for (template) |c|
        try addOrPut(&result, c, 1);

    var step: u8 = 0;
    while (step < 10) : (step += 1) {
        var tmp = AutoHashMap(Pair, usize).init(&fba.allocator);
        var items = count.iterator();
        while (items.next()) |entry| {
            const k = insertions.get(entry.key_ptr.*) orelse continue;
            const v = entry.value_ptr.*;
            try addOrPut(&tmp, k.left, v);
            try addOrPut(&tmp, k.right, v);
            try addOrPut(&result, k.left.right, v);
        }
        count.deinit();
        count = tmp;
    }

    var values = result.valueIterator();
    var max = values.next().?.*;
    var min = max;
    while (values.next()) |value| {
        max = math.max(value.*, max);
        min = math.min(value.*, min);
    }
    print("{}\n", .{ max - min });
}