Entrada:

Solução:
Gerador: