如果一個(gè)數(shù) x 的約數(shù)和 y （不包括他本身）比他本身小，那么 x 可以變成 y，y 也可以變成 x。例如 4 可以變?yōu)?3，1 可以變?yōu)?7。限定所有數(shù)字變換在不超過(guò) n 的正整數(shù)范圍內(nèi)進(jìn)行，求不斷進(jìn)行數(shù)字變換且不出現(xiàn)重復(fù)數(shù)字的最多變換步數(shù)。

輸入一個(gè)正整數(shù) n。

樣例說(shuō)明

一種方案為 4→3→1→7。

數(shù)據(jù)范圍與提示：

對(duì)于 100% 的數(shù)據(jù)，1≤n≤50000。

信息學(xué)一本通 動(dòng)態(tài)規(guī)劃