Background

Description

Given a string and a non-empty substring sub, compute recursively the largest substring which starts and ends with sub and return its length.

Format

Input

Output

Samples

catcowcat" "cat

9

catcowcat" "cow

3

cccatcowcatxx" "cat

9

Limitation

1s, 1024KiB for each test case.