B2. Тэгш өнцөгт тоглоом

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

ABBYY-ын Ухаалаг Минж нэг өдөр амрахаар шийдэв. Гэхдээ өдөржин юу ч хийхгүй байна гэдэг хэтэрхий уйтгартай байсан ба тэрээр хайрган чулуунуудаар тоглоом тоглохоор шийджээ. Анхандаа, Минж $n$ хайргатай байна. Тэрээр тэдгээрийн $a$ тэнцүү мөрнүүдэд байрлуулах ба мөр болгонд $b$ хайрга байна ($a > 1$). Минж бүх хайргуудаа ашиглах ёстойг анхаарна уу, өөрөөр хэлбэл $n = a*b$.

10 хайрга 2 мөрөнд байрласан ба мөр болгонд 5 хайрга байна.

Нэгэнт Ухаалаг Минж хайргуудыг байрлуулбал, тэрээр үр дүнгийн мөрнүүдийн аль нэгийг нь буцаан авах (энэ нь $b$ хайрга юм) ба бусад бүх хайргуудыг хаяна. Дараа нь тэрээр өөрийнхөө бүх хайргуудыг дахин байрлуулах ($a$ болон $b$-ын өөр утгууд сонгох боломжтой) ба нэг мөрийг буцаан авна гэх мэт үргэлжлэх юм. Тоглоом нь Минж яг нэг хайргатай дуусах хүртэл үргэлжилнэ.

Тоглоомын үйл явц нь бүхэл тоонууд $c_{1}, ..., c_{k}$-ын хязгаартай дарааллаар дүрслэгдэж болох ба энд:

  • $c_{1} = n$
  • $c_{i + 1}$ нь Минж-д $i$-дахь үйлдлийн дараа байх хайргын тоо ба иймд энэ нь $c_{i}$ хайргуудыг ямар нэгэн байдлаар байрлуулсны дараах нэг мөрөнд байх хайргын тоо юм ($1 ≤ i < k$). $c_{i} > c_{i + 1}$ болохыг анхаарна уу.
  • $c_{k} = 1$

Тоглоомын үр дүн гэдэг нь бүх $c_{i}$ тоонуудын нийлбэр юм. Танд $n$ өгөгдсөн. Тэгвэл боломжит хамгийн их тоглоомын үр дүнг олно уу.

Оролт

Ганц мөрөнд ганц бүхэл тоо $n$ өгөгдөнө -- энэ нь Ухаалаг Минж-д байх хайргуудын анхны тоог илэрхийлнэ.

30-н оноо авах оролтын хязгаар:

  • $2 ≤ n ≤ 50$

100-н оноо авах оролтын хязгаар:

  • $2 ≤ n ≤ 10^{9}$

Гаралт

Боломжит хамгийн их тоглоомын үр дүнг илэрхийлэх ганц тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
10
Гаралт
16
Оролт
8
Гаралт
15

Тэмдэглэл

Эхний жишээг авч үзье ($c_{1} = 10$). Тоглоомын явцын боломжит сонголтууд нь:

  • 10 мөрөнд хайргуудыг байрлуулах ба мөр болгонд нэг хайрга байна. Тэгээд $c_{2} = 1$ болох ба эхний үйлдлийн дараа 11 гэсэн үр дүнтэйгээр тоглоом дуусна.
  • 5 мөрөнд хайргуудыг байрлуулах ба мөр болгонд 2 хайрга байна. Тэгээд $c_{2} = 2$ болох ба тоглоом үргэлжилнэ. 2-дахь үйлдлийг хийхэд бидэнд цорын ганц замаар байрлуулж болох 2 хайрга байна (та бүх хайргаа ижил мөрөнд тавих нь зөвшөөрөгдөөгүй гэдгийг санана уу) -- энэ нь 2 мөрөнд байрлуулах ба мөр болгонд нэг хайрга байна. $c_{3} = 1$ ба 13 гэсэн үр дүнтэйгээр тоглоом дуусна.
  • Эцэст нь, 2 мөрөнд хайргуудыг байрлуулах ба мөр болгонд 5 хайрга байна. Ижилхэн логик биднийг $c_{2} = 5, c_{3} = 1$-т аваачих ба 16 гэсэн үр дүнтэйгээр тоглоом дуусна -- энэ нь боломжит хамгийн их үр дүн юм.
Сэтгэгдлүүдийг ачааллаж байна...