Background

Description

Given a string and a non-empty substring sub, compute recursively if at least n copies of sub appear in the string somewhere, possibly with overlapping. N will be non-negative.

Format

Input

Output

Samples

catcowcat" "cat" 

true

catcowcat" "cow" 

false

catcowcat" "cow" 

true

Limitation

1s, 1024KiB for each test case.