36 square rooms are arranged in a 6x6 grid. The outside wall of the grid has no doors. All other walls have exactly one door, for a total of 60 doors. A guard follows a path that takes him through as many doors as possible, never going through the same door twice (he may enter a room twice, as long as he uses different doors.) What is the maximum number of doors he can use if:
Extensions: Repeat for 3x3 to 8x8 grids.
Source: Original.