時間制限:1000ミリ秒
メモリ制限:65536KB
問題
Prime Path
4けたの素数がs,gが与えられる。
sのどれかの桁を一つだけ数字を変化させ、別の4桁の素数に変更する。
この操作を適当な回数繰り返してgを作れる時、sからgへの最小操作回数を求めよ。
1033を8179に変更する場合の最小回数の例。
1033
1733
3733
3739
3779
8779
8179
6回の操作で終了するので答えは6となる。
入力の最初の行はデータセットの数Tが与えられる。
一つのデータセットは一行で与えられ、s、gの2数が空白区切りで与えられる。
出力は、入力の各行に対して、最小操作回数を答えよ。
入力の例
3
1033 8179
1373 8017
1033 1033
出力の例
6
7
0
出典
Northwestern Europe 2006