C-tb的路径问题_牛客小白月赛101

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

tb 给了 fc 一张有 $n \times n$ 个格点的图。

图上每个格点都写着一个数。第 $i$ 行第 $j$ 列的格点上写着的数字为 $i$ 和 $j$ 的最大公约数。

现在 fc 需要从第 $1$ 行第 $1$ 列出发，去往第 $n$ 行第 $n$ 列处的格点，fc 可以消耗一点能量移向相邻的格点。

在任何时候，设 fc 所位于的格点上所写的数字为 $x$ ，如果 $x$ 不为 $1$ ，他可以使用传送阵传送到任何数字为 $x$ 的格点，此操作不消耗能量。

求 fc 到达第 $n$ 行第 $n$ 列所消耗的最少能量。

相邻：如果用 $(x,y)$ 表示第 $x$ 行第 $y$ 列的位置， $(x,y)$ 与 $(x+1,y),(x,y+1),(x-1,y),(x,y-1)$ 相邻。

输入描述:

一个正整数，表示  。

输出描述:

一个非负整数，表示最少能量。

示例1

输入

复制

输出

复制