Zadanie

Iné číslo

Počet bodov: 80

Matematici majú niekedy zvláštne nápady, a v horšom prípade s nimi ešte obťažujú informatikov. A presne to sa stalo aj v tejto úlohe.

Matúš je matematik a má nezáporné celé číslo \(n\). Matúš by však chcel mať číslo, ktoré by bolo deliteľné kladným celým číslom \(m\). Napadlo ho (lebo je matematik) že zmení niektoré cifry v tomto čísle. (Pozor, cifry bude len meniť, nesmie žiadne pridávať ani odoberať.)

Aby si Matúš neminul veľa papiera na výpočty, bolo by vhodné spraviť tých zmien čo najmenej.

Úloha

Pre dané \(n\) a \(m\) zistite, či vie Matúš povoleným spôsobom upraviť \(n\) na násobok \(m\), a ak áno, tak koľko najmenej cifier potrebuje zmeniť.

Formát vstupu

V jedinom riadku vstupu sú čísla \(n\) a \(m\).

Platí \(0\leq n\leq 10^{11}\) a \(1\leq m\leq 10^{11}\).

Formát výstupu

Vypíšte jediný riadok a v ňom jedno celé číslo. Ak Matúš nevie dosiahnuť svoj cieľ, vypíšte číslo -1 (mínus jedna). V opačnom prípade vypíšte ľubovoľné číslo, ktoré má vyrobiť: teda také číslo, ktoré je násobkom m, má rovnaký počet cifier ako číslo n a líši sa od čísla n na čo najmenej pozíciách. Vypísané číslo nesmie začínať zbytočnými nulami.

Príklady

Input:

123 10

Output:

120

Stačí jedna zmena: poslednú cifru z 3 na 0.

Input:

123 141

Output:

423

Opäť stačí jediná zmena, tentokrát na inej pozícii.

Input:

9 123

Output:

0

Samotná nula je špeciálnym prípadom, keďže nezačína zbytočnými nulami.

Input:

12 123

Output:

-1

Žiadne dvojciferné číslo nie je násobkom čísla 123.

Pre odovzdávanie sa musíš prihlásiť.