Canonical Coin System Test (1) X24976

Most coin systems currently or recently in use are canonical. This means that the greedy algorithm to reach a quantity always gives an optimal number of coins. Different systems such as dollars, euros, and also XX century pre-euro coins such as pesetas and Dutch Gulden, all have this property. However, not all coin systems have this property. The UK pound sterling system prior to Monday 15 February 1971 (see https://en.wikipedia.org/wiki/Decimal_Day) was a far cry from canonical. As a simpler example, with coins of 1, 5, and 8 units the greedy strategy fails to produce an optimal configuration to add up to 15; we say that this value is a counterexample to the canonicity of the system.

In 1993, Dexter Kozen and Shmuel Zaks proved mathematically that, if a system is not canonical, then a counterexample exists that is less than the sum of the two largest values in the system. This fact will allow you to distinguish canonical systems (but note that in later years more efficient algorithms were found).

Input

The input contains several cases of coin systems to test for canonicity. First, the input indicates the total number of cases, a non-negative integer n. Then, n cases follow: each case starts with m, a positive integer indicating the number of denominations, with m positive integers ordered increasingly corresponding to the denominations. The smallest denomination will always be 1 (coin systems lacking a 1-unit coin are never considered in the general literature, as they don’t allow one to pay a quantity of 1 unit).

Output

For each case, print a line. If the case is a canonical coin system, print the denominations of the case in ascending order followed by the words "is canonical" . If it is not, print the smallest counterexample, then the words "proves that", then the denominations of the case in ascending order, then the words "is not canonical".

Observation

The reference solution of this problem is somewhat "sluggish" and, hence, relatively slow solutions may get accepted anyway. The companion problem X88410 demands a more efficient solution of the same problem.