크기가 6×5×3인 직육면체 모양의 방 안 한쪽 구석에 거미(S)가 앉아 있고, 반대쪽 구석에는 파리(F)가 앉아 있습니다. 거미가 방의 표면을 가로질러서 파리에게 가는 가장 짧은 "직선" 경로의 거리는 아래 그림과 같이 10 이 됩니다.

하지만 일반적인 경우 가장 짧은 경로는 많게는 3개까지 있을 수 있고, 경로의 길이가 정수값이 아닐 수도 있습니다.

각 변의 길이가 모두 정수이고 최대 크기가 M×M×M 인 모든 직육면체에 대해서 최단 경로가 정수인 경우를 조사했을 때, M=100 이면 모두 2060가지가 있고 이것은 경우의 수가 2000이 넘는 최소의 M 값입니다 (M=99일 때는 1975).

그러면 이런 조건을 만족하는 직육면체의 수가 1백만을 넘는 최소의 M은 얼마입니까?