Top > 3126 Prime Path


3126 Prime Path

Last-modified: 2011-12-12 (月) 14:21:37

原文


時間制限:1000ミリ秒
メモリ制限:65536KB





問題 Edit

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数が空白区切りで与えられる。
出力は、入力の各行に対して、最小操作回数を答えよ。

入力の例 Edit

3
1033 8179
1373 8017
1033 1033

出力の例 Edit

6
7
0

出典 Edit

Northwestern Europe 2006