Rune Segmentation

In order to protect the forbidden magic recorded in an ancient grimoire, its author concatenated magical affixes without any spaces to form a rune string \(S\). All magical affixes used in \(S\) come from a mystical dictionary \(T\), where every non-empty prefix of \(T\) is considered a valid magical affix.

Since brevity is of the utmost importance in crafting the grimoire, the segmentation of \(S\) should use as few magical affixes as possible. In other words, given \(S\) and \(T\), you are to determine the minimum number of segments (each of which must be a non-empty prefix of \(T\)) that \(S\) can be divided into.

If no valid segmentation exists, then the grimoire is deemed fake. In that case, output Fake.

inputFormat

The input consists of two lines:

• The first line contains the rune string \(S\) formed by concatenating magical affixes.
• The second line contains the magical dictionary string \(T\). Every non-empty prefix of \(T\) is a valid magical affix.

outputFormat

If there is a valid way to segment \(S\), print the minimum number of segments. Otherwise, print Fake.

sample

abab
ab

2