本稿はCodeIQで2014年11月10日～2014年12月1日に出題された「一番割り算の多い組み合わせは？」という問題を再編集したものです。 ※出題時と記述が一部異なる場合がありますがご了承ください。

一番割り算の多い組み合わせは？

【問題】

ユークリッドの互除法は、2つの整数値の最大公約数を簡単に求める方法として有名です。たとえば、120と75の最大公約数を求めるとき、

120÷75 = 1 あまり 45
75÷45 = 1 あまり 30
45÷30 = 1 あまり 15
30÷15 = 2 あまり 0

のように、あまりが0になるところまで繰り返し割り算をすることで、最大公約数である15を得ることができます。

今回は、最大公約数ではなく、割り算の回数に注目してください。上記の例では、4回割り算を行うことで計算が終わりました。 4回の割り算が必要な値の組み合わせは、もっと小さな値でも見つかります。

8÷5 = 1 あまり 3
5÷3 = 1 あまり 2
3÷2 = 1 あまり 1
2÷1 = 2 あまり 0

このように8と5の場合でも、4回の割り算が必要です。

1からある整数nまでの間の数から2つの値を選び互除法の計算を行った際に、割り算の回数が最大になる値の組み合わせを答えてください。複数見つかった場合は、その中の1例のみで構いません。

nの値は、次の3種類とします。

(1) n=1234
(2) n=123456
(3) n=1234567890

これらの値は、コードの中に直接書き込んでいただいてもかまいませんし、実行時引数や標準入力からでも結構です。

上記の3例に対して、互除法の除算回数が最大になる場合の、「回数」と「その2数（大きい順）」を出力してください。