Masala #BX5XASY7WL

Freak Contaz Sequence - bu Collatz butun sonlar ketma-ketligining yana bir versiyasi bo'lib, a(1) dan quyidagi tarzda olinadi:

a(n + 1) = a(n) / 3, agar a(n) 3 ga boʻlinsa.
Biz buni katta pastga qadam sifatida belgilaymiz, "D".

a(n + 1) = (4 * a(n) + 2) / 3, agar a(n) 3 ga bo'linganda 1 qoldiq bo'lsa.
Biz buni yuqoriga qadam sifatida belgilaymiz, "U".

a(n + 1) = (2 * a(n) - 1) / 3, agar a(n) 3 ga bo'linganda 2 ning qoldig'i chiqadi.
Biz buni kichik pastga qadam sifatida belgilaymiz, "d".
Ba'zi k uchun a(k) = 1 bo'lganda ketma-ketlik to'xtaydi.

Har qanday butun sonni hisobga olgan holda, biz qadamlar ketma-ketligini sanab o'tishimiz mumkin:

Misol uchun, agar a(1) = 231 bo'lsa, {an} = {231,77,51,17,11,7,10,14,9,3,1} ketma-ketligi "DdDddUUdDD" bosqichlariga mos keladi.

Albatta, xuddi shu "DdDddUUdDD...." ketma-ketligi bilan boshlanadigan boshqa ketma-ketliklar ham bor.

Misol uchun, agar a = 1004064 bo'lsa, u holda ketma-ketlik "DdDddUUdDDDdUDUUUdDdUUDDDUdDD" bo'ladi.

Sizning vazifangiz N > 1 bo'lgan eng kichik musbat sonni topishdir, shunda ketma-ketlik s qatoridan boshlanadi. Ya'ni, agar s = "DdDddUUdDD" bo'lsa, natija 1004064 o'rniga 231 bo'lishi kerak.

Eslatma: a(1) = 1 uchun ketma-ketlik darhol tugaydi va 0 uzunlikdagi satr qaytariladi!

Birinchi qatorda s nomli string kiritiladi

Masalada so'ralgan javobni chop eting