John is a model railroad enthusiast. He enjoys these railroads so well that he wants to build them as long as possible. He also wants to meet other model railroad devotees and run their trains. To make it simple to transport his railroad and connect to various other railroads, each owner builds his railroad in modules. These modules are in specific sizes and designed to be easy to fit together.
John only builds rectangular modules. Every module has two connection points on the edge onto which other modules may be connected. In every module, the model railroad shall run between the two connection points, and the railroad must begin and end perpendicular to the wall at the connection points. To avoid too complex situations, John uses only straight rails and curved rails with a 90° bend. (A curved rail may be used to make either a left or a right turn.) A rail occupies an area of 10 × 10 centimeters whether the rail is curved or straight.
John want to design his railroads so that the track is as long as possible given the number of rails he has available. To achieve this, he wants to write a computer program that calculates how many rails he may use in a module.
An solution for a 6 × 4 module starting in (1, 1) and ending in (5, 4) when John has 15 straight and 5 curved railroad tracks.
The first input line specifies how many modules that are to be built. For every module the following information is given:
The answer shall be how long the longest legal railroad can be. If it is impossible to build a railroad, you should state this.
2 6 4 1 5 15 5 4 4 1 4 10 1
Module 1: Longest railroad has 14 rails. Module 2: No such railroad.