Паук S сидит в одном углу комнаты в форме прямоугольного параллелепипеда размерами 6 на 5 на 3, а муха F сидит в противоположном углу. Путешествуя по поверхностям комнаты, кратчайший путь "по прямой" от S до F имеет длину 10 и показан на рисунке ниже.

Однако, в любом прямоугольном параллелепипеде существует до трех кандидатов на "кратчайший" путь, и кратчайший путь не всегда имеет целую длину.

Рассматривая все комнаты в форме прямоугольного параллелепипеда с максимальными размерами M на M на M, существует ровно 2060 прямоугольных параллелепипедов, для которых кратчайшее расстояние - целое число, при M = 100, и это - наименьшее значение M, при котором количество решений превышает две тысячи: при M = 99 количество решений равно 1975.

Найдите наименьшее значение M, при котором количество решений превышает один миллион.