Bajtazar is opening a new warehouse. He would like a large sign with a certain inscription to hang above the entrance. This inscription should contain the name of his company as a contiguous substring as many times as possible, where these occurrences may overlap.

Taught by experience, Bajtazar knows he must watch out for vandals who destroy signs. He fears that hooligans might try to erase some letters from the sign in such a way that the remaining (unerased) letters form the name of a competing company. He would therefore like to choose the inscription on the sign such that this is not possible. Can you help him?

Input

The first line of input contains a word that is the name of Bajtazar's company. The second line of input contains a word that is the name of the competing company. Both words are non-empty and consist of lowercase and/or uppercase English letters and/or digits. Note: case sensitivity applies when comparing strings.

Output

The first and only line of output should contain a single integer – the maximum possible number of occurrences of Bajtazar's company name in an inscription that satisfies the problem conditions.

If Bajtazar's company name can appear in the inscription an arbitrarily large number of times, output the word INF instead.

Examples

Input 1

karolek
lololek

Output 1

2

Note

Bajtazar can place, for example, the inscription karolekarolek on the sign. Placing the word karolek three times on the sign inevitably leads to the possibility of erasing some letters so that the word lololek remains.

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups. Let $n$ denote the constraint on the length of both company names.