FMI NO STRESS 13 | aiacusumacifrelor

This was the problem page during the contest. Access the current page here.
Time limit: 0.6s Memory limit: 256MB Input: Output:

Cerință

Se dă un număr natural QQ și QQ numere naturale xx, cărora li se pot aplica un număr arbitrar de transformări. O transformare constă în următoarele tipuri de operații:

  • Adunare sau înmulțire cu 22 (xx+2x \leftarrow x + 2 sau xx2x \leftarrow x \cdot 2);
  • Adunare sau înmulțire cu 33 (xx+3x \leftarrow x + 3 sau xx3x \leftarrow x \cdot 3);
  • Adunare sau înmulțire cu 55 (xx+5x \leftarrow x + 5 sau xx5x \leftarrow x \cdot 5);
  • Adunare sau înmulțire cu 77 (xx+7x \leftarrow x + 7 sau xx7x \leftarrow x \cdot 7).

Pentru fiecare număr din cele QQ date, se cere numărul minim de transformări care trebuie aplicate astfel încât suma cifrelor numărului rezultat să fie divizibilă cu 99.

Date de intrare

Pe prima linie se găsește un număr natural QQ. Pe fiecare din următoarele QQ linii se găsește câte un număr natural xx.

Date de ieșire

Pe linia ii se va afișa numărul minim de transformări aplicate celui de-al ii-lea număr.

Restricții și precizări

  • 1Q1051 \leq Q \leq 10^5;
  • 1x10181 \leq x \leq 10^{18};
  • Pentru teste în valoare de 7070 de puncte, 1x1091 \leq x \leq 10^9;
  • Pentru alte teste în valoare de 3030 de puncte, nu există restricții suplimentare.

Exemplu

stdin

3
4
9
23895793

stdout

1
0
2

Explicație

Pentru x=4x = 4, acesta se poate aduna cu 55, obținând astfel 99.
Pentru x=9x = 9, acesta are deja suma cifrelor divizibilă cu 99.
Pentru x=23895793x = 23895793, aplicăm două transformări:

  1. xx+2x \leftarrow x + 2, acesta devenind egal cu 2389579523895795;
  2. xx3x \leftarrow x \cdot 3, acesta devenind egal cu 7168738571687385, care are suma cifrelor 4545.

Log in or sign up to be able to send submissions!