Digit Transformation

Given an integer \(n\) and \(k\) transformation rules, each rule specifies that a single digit can be transformed into another single digit. Note that the right-hand side of any transformation rule cannot be zero.

You can apply any transformation any number of times (including zero times). A transformation rule \(a \longrightarrow b\) means that if a digit in \(n\) is \(a\), you may change it to \(b\). Any digit can remain unchanged as well.

For example, let \(n = 234\) and \(k = 2\) with the following rules:

• \(2 \longrightarrow 5\)
• \(3 \longrightarrow 6\)

The possible integers obtained (including the original number) are:

• 234
• 534
• 264
• 564

Thus, there are 4 distinct integers. Given \(n\) and \(k\) transformation rules, determine how many distinct integers can be produced by applying the rules arbitrarily many times.

inputFormat

The first line contains a string \(n\) representing the integer and an integer \(k\) representing the number of transformation rules.

Then follow \(k\) lines, each containing two space-separated digits \(a\) and \(b\), representing the transformation rule \(a\longrightarrow b\). Note that \(b\) will never be 0.

outputFormat

Output a single integer: the number of distinct integers that can be obtained by applying the rules arbitrarily many times (including possibly zero transformations).

sample

234 2
2 5
3 6

4