Nick is playing Dance Dance Revolution!

Dance Dance Revolution is a game where players step on notes to the rhythm of music. Players can step either left, down, up, or right. In the real game, it is possible to step in two or more directions at the same time, but Nick is not good enough to do that yet so he only plays charts where players step in one direction at a time.

Nick wants to practice a specific pattern of steps ~p~, which is a sequence of directions. He is in the practice mode of Dance Dance Revolution which has a predetermined sequence of notes ~s~. Nick wants to practice the pattern ~p~ as many times as possible, so he will intentionally choose for each note in the sequence whether to step on it or skip it.

Nick wants to maximize the number of times he performs the given pattern of steps. The pattern must be performed in an unbroken sequence with no steps in between, and a given note can only be in at most one instance of the pattern.

Constraints

~1 \le |p| \le |s| \le 10^3~

Each letter in ~p~ or ~s~ comes from LDUR.

Input Specification

The first line contains the sequence of notes ~s~ that practice mode has loaded.

The second line contains the pattern of notes ~p~ that Nick wants to practice.

Output Specification

Output a single integer, the maximum number of times Nick can perform his desired pattern.

Sample Input 1

LRLDLRL
LRL

Sample Output 1

2

Sample Explanation 1

If Nick doesn't change the notes he hits at all, he will perform the LRL pattern twice. It is impossible for him to perform it three times.

Sample Input 2

LRLRL
LRL

Sample Output 2

1

Sample Explanation 2

Even though LRL technically appears twice in the pattern, the two appearances overlap. Therefore, Nick can only be considered to perform the LRL pattern once.

Sample Input 3

UDUDUDUDU
UU

Sample Output 3

2

Sample Explanation 3

If Nick ignores every down arrow, he will perform the sequence UUUUU. In this sequence, Nick can perform the UU pattern twice. It is impossible for Nick to perform the UU pattern more than two times.