M<=10^9
だからTLEの危険もあったのかな。

m/n以下の数で順に割って無事に通ったが。