The Code Goddess is angry with her disciple Somnath because he dared to defy her orders. Somnath being scared of her has hidden his location in a encrypted safe having N^2 encryption levels numbered from 1 to N. The encryption levels are arranged randomly in a NxN grid. Using her Godly Powers, The Code Goddess came to know that the each encryption level contains the key to the next encryption level i.e. level 2 consists the key for encryption level 3 and so on. In general level K has the key for level K+1. The Encryption level N^2 has Somnath’s location.

The Code Goddess who wants to unleash her wrath on Somnath has easily broken into Level 1. However being The Code Goddess she wants to breaks Somnath’s encryption systematically. From Level 1 she will move to any one of the adjacent encryption level in the grid and can break an encryption level only when she has the key. Two levels are considered adjacent if they are next to each other on the grid. Since she moves slowly, it takes her 30 seconds to move to an adjacent encryption level and negligible time to break it.

Find out the minimum time she needs to discover Somnath’s location.

Input Format

The first line contains N. The next N line shows the arrangement on the encryption grid.

Output Format

Print a single line with time she needs in the format:

HH:MM:SS

Constraints

2 <= N <=  300