6879번 - Pyramid Message Scheme 다국어

Spamway Inc. maintains a network of zombie computers to solicit and collect orders for its various fine products. Each zombie computer is responsible for zero or more subordinate zombies that it coordinates in these activities.

Spamway uses a simple communication strategy among its zombies for transmitting solicitations and receiving orders. Each solicitation originates at Spamway's head zombie, which then communicates it to each of its subordinates in turn, waiting to collect orders from one subordinate before proceeding to the next. Each subordinate employs the same strategy - it sends to and receives from each of its subordinates in turn.

For example, suppose that Home has two subordinate zombies named Alfred and Betty; Alfred's subordinates are named Cindy and Dennis; Betty has no subordinates. This organization is pictured below.

            Cindy
           /
     Alfred
    /      \
Home        Dennis
    \
     Betty

Home first sends to Alfred; Alfred then sends to Cindy; Cindy responds to Alfred; Alfred sends to Dennis; Dennis responds to Alfred; Alfred responds to Home; Home sends to Betty; Betty responds to Home.

Each message takes $10$ seconds to be delivered. So the example given above would be completed in $80$ seconds. You have been retained by Spamway, who will pay you handsomely (in Spam Bucks which may be redeemed for any of their valuable products) to help them reduce the time necessary to solicit and collect orders. In particular, Spamway is considering a new strategy in which each zombie sends out messages to each of its subordinates and waits for their responses only after all messages have been sent.

Spamway's network administrator has captured a chronological list of the name of the recipient of each message involved in a particular solicitation. For the example above, using the slow strategy, this list would be: Alfred, Cindy, Alfred, Dennis, Alfred, Home, Betty, Home. (Note that $8$ messages at $10$ seconds per message is $80$ seconds.)

Using the new and improved strategy, Home sends to Alfred and Betty simultaneously, Alfred sends to Cindy and Dennis at the same time as Betty is responding, Cindy and Dennis respond simultaneously to Alfred and finally Alfred responds to Home. Using the new strategy, Spamway needs only $40$ seconds to accomplish the communication that takes $80$ seconds using the old strategy. Thus, Spamway can send twice as many solicitations and make twice as much money.

As input, you are given lists of names describing the order that messages are received using the old Spamway strategy. The input contains the integer $L$, followed by $L$ message lists. Each list begins with an integer, $n$, identifying the number of message recipients in the list, followed by $n$ lines, each containing the name of a message recipient.

For each list you are to print out a single integer indicating the amount of time in seconds that Spamway saves.