Enumerate Substrings

Problem Background

Special for beginners, ^_^

Problem Description

Given a string containing only 0 and 1 (length between $1$ and $100$), find how many times each of its substrings occurs.

Input Format

One line: a string of 0s and 1s.

Output Format

For every substring that occurs more than once, output the substring and its count, separated by a single space. Output in ascending lexicographic order of the substrings, one per line.

Sample Input

10101

Sample Output

0 2
01 2
1 3
10 2
101 2

Constraints

1s, 1024KiB for each test case.