he year is 2050. The population surge has taken over our metropolitan cities. High rise buildings are on a rise. And as usual, with the increase in population, the problem of parking in the city has increased manifold.

To reduce the problem of parking, the government has built multi-storey parking lots all over the city. Imagine the city as an X-Y grid. And there are roads connecting all the neighbouring grid points except diagonals. And there is a pre-defined intersection interval 'I' for parking lots such that at every I th intersection, there is a parking lot, starting from (0,0). For example, for a city of grid size 4x7 and I=3, you'll have 6 parking lots at (0,0), (0,3), (0,6), (3,0), (3,3) and (3,6).