모형 철도

John은 모형 철도 애호가입니다. 그는 철도를 무척 좋아해서 가능한 한 길게 만들고 싶어 하고, 다른 애호가들과 연결해 서로의 기차를 달리게 하고 싶어 합니다. 철도를 쉽게 운반하고 다른 철도와 연결할 수 있도록, 각 소유자는 자신의 철도를 표준 규격의 모듈(module) 단위로 만듭니다. 이 모듈들은 서로 깔끔하게 맞물리도록 설계되어 있습니다.

John은 직사각형 모듈만 만듭니다. 모든 모듈에는 가장자리에 정확히 두 개의 연결점이 있으며, 하나는 아래쪽 변에, 다른 하나는 위쪽 변에 있습니다. 모듈 안에서 선로는 이 두 연결점 사이를 지나가고, 각 연결점에서는 벽에 수직으로 시작하고 끝나야 합니다.

단순함을 위해 John은 두 종류의 선로만 사용합니다. 직선 선로와 90°로 꺾이는 곡선 선로입니다(곡선 선로는 왼쪽이나 오른쪽 어느 쪽으로든 돌 수 있습니다). 직선이든 곡선이든 선로 하나는 10 × 10 cm 넓이의 정사각형을 차지합니다.

John은 가진 선로 개수 안에서 각 모듈의 선로를 가능한 한 길게 만들고 싶어 합니다. 한 모듈에 놓을 수 있는 선로의 최대 개수를 구하는 프로그램을 작성하세요.

John이 직선 선로 15개와 곡선 선로 5개를 가지고 있을 때, (1, 1)에서 시작해 (5, 4)에서 끝나는 6 × 4 모듈의 한 가지 해답입니다.

첫 번째 줄에는 만들 모듈의 개수가 주어집니다. 이어서 각 모듈은 세 줄로 설명됩니다.

1. 모듈의 크기: 두 정수 너비(width)와 깊이(depth)로, 10 cm의 배수 단위(즉 각 변의 칸 수)로 주어집니다. 두 값 모두 10 이하입니다.
2. 두 연결점의 x좌표: 아래쪽 행의 연결점, 그다음 위쪽 행의 연결점 순서로 주어집니다. 각 x좌표는 1부터 너비까지의 정수입니다.
3. 이 모듈에 사용할 수 있는 직선 선로의 개수와 곡선 선로의 개수입니다.

모듈은 너비 × 깊이 개의 칸으로 이루어진 격자이며, 각 칸은 10 × 10 cm 크기이고 한 칸에는 선로를 최대 한 개만 놓을 수 있습니다. 선로는 어떤 칸도 다시 지나지 않는 칸들의 경로이며, 아래쪽 연결점 칸으로는 아래 벽에 수직으로 들어오고 위쪽 연결점 칸에서는 위 벽에 수직으로 나갑니다. 선로가 곧게 지나가는 칸은 직선 선로 한 개를, 90°로 꺾이는 칸은 곡선 선로 한 개를 사용합니다.

각 모듈마다 한 줄을 출력합니다.

선로를 놓을 수 있으면 Module i: Longest railroad has N rails.를 출력합니다. 여기서 i는 모듈 번호(1부터 시작)이고 N은 놓을 수 있는 선로의 최대 개수입니다.

가진 선로로는 올바른 선로를 전혀 놓을 수 없으면 Module i: No such railroad.를 출력합니다.