Background

Description

Given a string and a non-empty substring sub, compute recursively the number of times that sub appears in the string, without the sub strings overlapping.

Format

Input

Output

Samples

catcowcat" "cat

2

catcowcat" "cow

1

catcowcat" "dog

0

Limitation

1s, 1024KiB for each test case.