Once upon a time, there lived a dumb king. He always messes things up based on his whimsical ideas. This time, he decided to renew the kingdom’s coin system. Currently the kingdom has three types of coins of values 1, 5, and 25. He is thinking of replacing these with another set of coins.
Yesterday, he suggested a coin set of values 7, 77, and 777. “They look so fortunate, don’t they?” said he. But obviously you can’t pay, for example, 10, using this coin set. Thus his suggestion was rejected.
Today, he suggested a coin set of values 1, 8, 27, and 64. “They are all cubic numbers. How beautiful!” But another problem arises: using this coin set, you have to be quite careful in order to make changes efficiently. Suppose you are to make changes for a value of 40. If you use a greedy algorithm, i.e. continuously take the coin with the largest value until you reach an end, you will end up with seven coins: one coin of value 27, one coin of value 8, and five coins of value 1. However, you can make changes for 40 using five coins of value 8, which is fewer. This kind of inefficiency is undesirable, and thus his suggestion was rejected again.
Tomorrow, he would probably make another suggestion. It’s quite a waste of time dealing with him, so let’s write a program that automatically examines whether the above two conditions are satisfied.
The input consists of multiple test cases. Each test case is given in a line with the format
n c1 c2 . . . cn
where n is the number of kinds of coins in the suggestion of the king, and each ci is the coin value.
You may assume 1 ≤ n ≤ 50 and 0 < c1 < c2 < . . . < cn < 1000.
The input is terminated by a single zero.
For each test case, print the answer in a line. The answer should begin with “Case #i: ”, where i is the test case number starting from 1, followed by
3 1 5 25 3 7 77 777 4 1 8 27 64 0
Case #1: OK Case #2: Cannot pay some amount Case #3: Cannot use greedy algorithm