A duke loved to invite his friends to hunt pheasant on his estate. His gamekeeper was responsible for stocking the woods with plump birds. He kept one hundred pheasants each locked in its own cage to protect against poachers. The cages were numbered from 1 to 100. Each cage had a lock that opened when the key was turned once, and locked again when when it was turned a second time.

The gamekeeper began feeling sorry for his charges. One night, while the birds slept, he quietly unlocked all 100 cages. At once he began worrying that the duke would be furious and immediately went back and turned the locks again on every second lock (2, 4, 6, ...), thereby locking them.

Thinking that he had still freed too many birds, he gave every third lock a turn (3, 6, 9, ...), then every fourth lock, then every fifth lock, sixth lock, and so on, all the way to the "every 100th" lock. He finished just in time, as dawn was breaking, and the birds were beginning to waken.

Your task is to find:

Extra: Which cages(s) was (were) switched the most times?