Description

Original source: ACM Pacific NW Region 1998

Given a set of digit strings, determine whether any string is a prefix of another.

Input Format

The input consists of multiple test cases, each ending when the digit 9 is encountered.

Output Format

For each test case, if no string is a prefix of another, output Set t is immediately decodable; otherwise, output Set t is not immediately decodable, where t is the test case number (starting from 1).

Sample 1

01
10
0010
0000
9
01
10
010
0000
9

Set 1 is immediately decodable
Set 2 is not immediately decodable

Constraints & Notes

The original problem statement reads:

An encoding of a set of symbols is said to be immediately decodable if no code for one symbol is the prefix of a code for another symbol. We will assume for this problem that all codes are in binary, that no two codes within a set of codes are the same, that each code has at least one bit and no more than ten bits, and that each set has at least two codes and no more than eight.

Each digit string consists only of 0 and 1, with length l satisfying 1 ≤ l ≤ 10. Each test case contains at least 2 and at most 8 digit strings.