Problem G
Saving the Universe
The urban legend goes that if you go to the Google homepage and search for "Google", the universe will implode. We have a secret to share... It is true! Please don’t try it, or tell anyone. All right, maybe not. We are just kidding.
The same is not true for a universe far far away. In that universe, if you search on any search engine for that search engine’s name, the universe does implode!
To combat this, people came up with an interesting solution. All queries are pooled together. They are passed to a central system that decides which query goes to which search engine. The central system sends a series of queries to one search engine, and can switch to another at any time. Queries must be processed in the order they’re received. The central system must never send a query to a search engine whose name matches the query. In order to reduce costs, the number of switches should be minimized.
Your task is to tell us how many times the central system will have to switch between search engines, assuming that we program it optimally.
Input
The first line of the input file contains the number of
cases,
Each case starts with the number
The following line contains a number
You may assume that
Output
For each input case, you should output:
Case #X: Y
where
Do not count the initial choice of a search engine as a switch.
Sample Input 1 | Sample Output 1 |
---|---|
2 5 Yeehaw NSM Dont Ask B9 Googol 10 Yeehaw Yeehaw Googol B9 Googol NSM B9 NSM Dont Ask Googol 5 Yeehaw NSM Dont Ask B9 Googol 7 Googol Dont Ask NSM NSM Yeehaw Yeehaw Googol |
Case #1: 1 Case #2: 0 |