In a chess game, a knight can move two squares vertically and one square horizontally, or two squares horizontally and one square vertically. In this problem, you need to find the smallest number of moves the knight needs to take to reach the star $\text{'}**\text{'}$ in the board. This is a brute force problem where you need to attempt and track different paths of the knight. For example, for the given position of the knight at $(0,0)$ and the star position at $(5,6),$ the smallest number of required moves is $5.$

The required moves are tracked as follows:

$\backslash$table$[[K,3,2,3,2,3,4,.],[3,4,1,2,3,4,3,4],[2,1,4,3,2,3,4,.],[3,2,3,2,3,4,3,4],[2,3,2,3,4,3,4,.],[3,.,3,.,3,.,***,.],[.,3,.,3,.,.,.,.],[.,.,.,.,.,.,.,.]]$

If the star position cannot be reached, the program should print a $-1.$ This rule applies also in case the starting or the last position is out of bound of the board.

Input Format

Sample input: $0056$