Web Service Dependencies

Docker is an open platform for building, shipping and running distributed applications as lightweight containers. Think of a container as a lightweight virtual machine that runs in user mode. Amazon's EC2 Container Service (ECS) uses Docker containers to build a higher-level abstraction called a task. A task is one or more containers together with their dependencies, and ECS launches those containers in a correct order. A container can be launched only when every container it depends on is already running. Amazon wants to compare performance across different valid launch orders, so ECS needs to know how many valid launch orders exist. Count them for each configuration.

The first line contains the number of configurations $N$ ($1 \le N \le 100$).

The first line of each configuration contains an integer $M$ ($1 \le M \le 12$), the number of containers. Each of the next $M$ lines contains a space-separated list of alphanumeric names. The first name on a line is a container, and the remaining names on that line are the containers it depends on, given in arbitrary order.

Every name is at most 10 characters long, and names are case-sensitive. Each of the $M$ containers appears as the first name of exactly one line, and every name written as a dependency is one of those $M$ containers. The same dependency may appear more than once on a line, and a line may name its own container as a dependency.

For each configuration print Case #n: , where $n$ is the configuration number starting at 1, followed by the number of valid launch orders. Print 0 when no valid order exists.