Пятнашки

Limits: 2 sec., 256 MiB

Мабуть усі в дитинтстві бавилися у відому гру — пятнашки. Правила дуже прості: ігрове поле складається з восьми квадратиків, пронумерованих від 1 до 8 і пустого місця. За один хід на пусте місце можна поставити сусідній по горизонталі або вертикалі квадратик. Ціль гри досягкути таку позицію (0 означає порожнє місце):

123
456
780

Петрик також полюбляє цю гру, але часто в нього навіть після кількох годин не виходить досягнути цільової позиції. Допоможіть Петрику.

Input

Задана початкова ігрова позиція — 3 рядки по 3 числа, не розділених пробілами. Числа від 0 до 8.

Output

У єдиному рядку виведіть одне ціле число — мінімальну кількість ходів, за яку можна досягнути цільову позицію, або -1 якщо цільову позицію досягнути не вдасться.

Samples