DouKaku?

中高生向けの情報オリンピックの国内予選2007年度の問題4です。

問題内容： http://www.ioi-jp.org/joi/2007/2008-yo-prob_and_sol/2008-yo-t4/2008-yo-t4.html

注意事項： http://www.ioi-jp.org/howtolearn.html

テストデータと解説： http://www.ioi-jp.org/joi/2007/2008-yo-prob_and_sol/index.html

「問題ごとに、プログラムの実行時間（や使用メモリ量）に制限が設定されています。」にご注意ください。特に記載されていませんが、本問題は計算が10秒以内に終了するように工夫する必要があります。

問題文末尾のテストデータは出題時には公開されていません。採点は、5つのテストデータにおいて制限時間内に正しい結果が返ってくるかで採点されます。入力は標準入力から、出力は標準出力にて行います。