European railroad tracks

Different countries in Europe use different railroad systems. Not only do their trains run on different voltages, but the distance between the two rails (the gauge) also varies from country to country. The table below lists some of the railway gauges actually in use.

A museum exhibits trains from several countries. To show visitors the trains sitting on a track, it needs a suitable gauge for every train. Because only one train is displayed at a time, a single rail may be shared by trains of different types. Hence, for $n$ trains that each require a different gauge, $n + 1$ rails are always enough (every train uses the leftmost rail together with the rail that lies exactly its required gauge away). Sometimes, however, even fewer rails suffice.

The rails are placed at distinct positions along one straight line, and a train may use any two rails whose spacing is exactly equal to its required gauge. Given the required gauges, determine the minimum number of rails needed to build a track that every train can use.

The first line contains the number of test cases. Each test case begins with a line containing $n$, the number of distinct required gauges. The next line contains $n$ integers between $1000$ and $5000$, each giving one required gauge.

You may assume $1 \le n \le 8$. Moreover, every test case in the input is guaranteed to be solvable with at most $5$ rails.

For each test case, print two lines. The first line has the form Scenario #X, where X is the test case number starting from $1$. The second line contains the minimum number of rails needed to build a track usable by every train.

Print one blank line between the outputs of two consecutive test cases.