유럽의 철도 궤도

유럽의 여러 나라는 서로 다른 철도 시스템을 사용한다. 열차에 쓰는 전압뿐 아니라 두 레일 사이의 간격(궤간, gauge)도 나라마다 다르다. 다음 표는 실제로 쓰이는 몇 가지 궤간이다.

한 박물관이 여러 나라의 열차를 전시한다. 관람객에게 열차가 선로 위에 놓인 모습을 보여 주려면 열차마다 알맞은 궤도가 필요하다. 그런데 한 번에 한 대의 열차만 전시하므로, 하나의 레일을 서로 다른 종류의 열차가 함께 쓸 수 있다. 따라서 서로 다른 궤간을 요구하는 열차 $n$대가 있으면 레일 $n + 1$개로 충분하다(각 열차가 가장 왼쪽 레일과, 그 레일에서 필요한 간격만큼 떨어진 레일을 함께 쓰면 된다). 하지만 때로는 레일을 더 줄일 수도 있다.

레일들은 한 직선 위의 서로 다른 위치에 놓이며, 열차는 두 레일 사이의 간격이 자신이 요구하는 궤간과 정확히 같기만 하면 임의의 두 레일을 사용할 수 있다. 요구되는 궤간들이 주어질 때, 모든 열차가 사용할 수 있는 궤도를 만드는 데 필요한 레일의 최소 개수를 구하여라.

첫 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫 줄에는 필요한 서로 다른 궤간의 개수 $n$이 주어진다. 다음 줄에는 $1000$ 이상 $5000$ 이하의 정수 $n$개가 주어지며, 각각이 요구되는 하나의 궤간을 나타낸다.

$1 \le n \le 8$이다. 또한 입력의 모든 테스트 케이스는 레일 $5$개 이하로 해결할 수 있음이 보장된다.

각 테스트 케이스마다 두 줄을 출력한다. 첫 줄은 Scenario #X 형식이며, 여기서 X는 $1$부터 시작하는 테스트 케이스 번호이다. 둘째 줄에는 모든 열차가 사용할 수 있는 궤도를 만드는 데 필요한 레일의 최소 개수를 출력한다.

서로 다른 두 테스트 케이스의 출력 사이에는 빈 줄을 하나 넣는다.