== include(page="template/taskheader" task_id="voodoo") ==

Georgian lucrează la un proiect Voodoo, până când i-a venit în cap o problemă ezoterică cu nişte funcţii la fel de ezoterice.

Georgian lucra la un proiect Voodoo, până când i-a venit în cap o problemă ezoterică cu nişte funcţii la fel de ezoterice.

Fie un număr $x$, căruia vrem să îi calculăm cifra de control în baza $B$. Aceasta se poate calcula folosind următorul algoritm:
==code(c) |
// vrem să calculăm cifra de control a lui x în baza B.
int cfcontrol(int x, int B) {

  while(x >= B)      // Atâta timp cât x are doua sau mai multe cifre în baza B.
    x = sumcf(x, B); // Înlocuim pe $x$ cu suma cifrelor sale în baza B. (*)

  while(x >= B)      // Atâta timp cât x are două sau mai multe cifre în baza B.
    x = sumcf(x, B); // Înlocuim pe x cu suma cifrelor sale în baza B. (*)

  return x; // Rezultatul final va fi valoarea stocată în variabila x.
}

// Notă: Numerele pot ajunge foarte mari. Vom presupune aici că tipul de date int poate stoca numere oricât de mari, nu doar până la 2^31 - 1.

==
Se definesc următoarele două funcţii $F{~B~}$ şi $G{~B~}$.

$F{~B~}(n)$ va fi numărul de ori în care se calculeză suma cifrelor în apelul funcţiei $cfcontrol(n, B)$, adică de câte ori se execută linia a 4-a din program (marcată cu $(*)$).

$F{~B~}(n)$ va fi numărul de dăţi în care se calculeză suma cifrelor în apelul funcţiei $cfcontrol(n, B)$, adică de câte ori se execută linia a 4-a din program (marcată cu $(*)$).

$G{~B~}(n) = x$ unde $x$ este cel mai mic număr natural nenul în care $F{~B~}(x) = n$.
În următorul tabel sunt prezentate mai multe exemple de calcul al cifrei de control şi al funcţiei F{~B~}.

* $B$ *nu* va fi de forma $6k + 1$ sau $9k + 1$ oricare ar fi $k$ număr întreg
* $1 ≤ M ≤ 3^12^$
* $M$ este de forma $3^k^$ unde $k$ este un număr întreg

* Pentru teste în valoare $20$ de puncte, $G{~B~}(N) ≤ 10^18^$
* Pentru alte teste în valoare $50$ de puncte, $N ≤ 250.000$

* Haos.
h2. Exemplu

| 3 9 27
| 26
|

| Exemplu haos input
| Exemplu haos output

| 250000 5007329433060514 531441
| 425803
|
| 1000000000000000000 5007329433060514 531441
| 384844

|
h3. Explicaţie

În al doilea exemplu, răspunsul este $161{~(10)~} = 188{~(9)~}$. Suma cifrelor lui $188{~(9)~}$ este $1 + 8 + 8 = 17 = 18{~(9)~}$. Suma cifrelor lui $18{~(9)~}$ este $1 + 8 = 9 = 10{~(9)~}$. Suma cifrelor lui $10{~9~}$ este $1 + 0 = 1$. Am calculat suma cifrelor de $3$ ori, deci $F{~9~}(161{~(10)~}) = 3$. Acesta este cel mai mic număr pentru care se obţine rezultatul respectiv. $161 modulo 27$ va fi $26$.

Al treilea exemplu este prea voodoo pentru a explica aici.

Ultimele două exemple sunt prea haos pentru a avea o explicaţie.

== include(page="template/taskfooter" task_id="voodoo") ==