Pyramid Message Scheme

A company called Spamway runs a network of zombie computers to solicit and collect product orders. Each zombie computer coordinates zero or more subordinate zombies, so the zombies form a tree: the head zombie is the root, and every other zombie has exactly one direct supervisor.

Under the original strategy, every solicitation starts at the head zombie, which contacts each of its subordinates one at a time. It sends a message to a subordinate, waits until that subordinate's entire subtree has reported back, and only then moves on to the next subordinate. Every zombie follows the same rule with its own subordinates.

For example, suppose the head zombie Home has two subordinates, Alfred and Betty. Alfred has two subordinates, Cindy and Dennis, while Betty has none:

            Cindy
           /
     Alfred
    /      \
Home        Dennis
    \
     Betty

Home first sends to Alfred; Alfred sends to Cindy; Cindy replies to Alfred; Alfred sends to Dennis; Dennis replies to Alfred; Alfred replies to Home; Home sends to Betty; Betty replies to Home.

Each message takes $10$ seconds to deliver, so this example finishes in $80$ seconds ($8$ messages).

Spamway now considers a faster strategy: each zombie first sends messages to all of its subordinates and only afterward waits for all of their replies. A zombie contacts all of its subordinates simultaneously, so those sends together take $10$ seconds, the subtrees are then processed in parallel, and the replies also come back in parallel.

Applying the improved strategy to the same example: Home sends to Alfred and Betty at once; Alfred sends to Cindy and Dennis while Betty is replying to Home; Cindy and Dennis reply to Alfred simultaneously; finally Alfred replies to Home. The improved strategy needs only $40$ seconds instead of $80$.

The network administrator recorded, in chronological order, the recipient of every message during a single solicitation under the original strategy. For the example above this recipient list is: Alfred, Cindy, Alfred, Dennis, Alfred, Home, Betty, Home.

Given such a recipient list, determine how many seconds the improved strategy saves compared with the original one.

The first line contains an integer $L$, the number of recipient lists. Each list starts with a line containing an integer $n$, the number of messages in that list, followed by $n$ lines, each holding the name of one message recipient in chronological order. Different zombies always have different names, so each name refers to exactly one zombie. (A single name can still appear several times in a list, since a zombie is named once for each message it sends or receives.)

For each list, print a single integer on its own line: the number of seconds saved by using the improved strategy instead of the original one.