Мињоните се малечки, интересни, сложни суштества со невидено гооолема интелигенција. Дарко е мињонче кое е премногу мало за да зборува, но доволно паметно за да знае да користи калкулатор. Кога другите мињони го прашувале Дарко нешто на коешто тој можел да одговори со број, тој го типкал бројот на калкулаторот и им го покажувал на другите мињони.

Но, од прекумерно користење, денес на калкулаторот на Дарко функционираат само одреден број на цифри, и само операциите множење и собирање.

Калкулаторот на Дарко работи само со релативно малечки броеви (од 0 до 5000), па доколку резултатот од некоја операција (множење или собирање) е поголем од 5000, калкулаторот автоматски му запишува 5000. Дарко не може да запише број поголем од 5000 (ако проба да запише 7777, калкулаторот нема да му дозволи да ја запише последната седмица, и ќе покажува 777).

Ваша задача е да му помогнете на мињончето да открие кој е минималниот број на операции со кои може да се изрази даден број N. За операција се смета запишување на цифра од број, собирање и множење. Така изразот 2*22+2 има вкупно 6 операции. Додека не се внесе барем една цифра, калкулаторот не покажува ништо.

Внимавајте, множењето има предност над собирањето.

Влез

Во првиот ред се запишани цифрите кои функционираат на калкулаторот на Дарко (дадени како текстуална низа од цифри '0'-'9', без празни места, и подредени во опаѓачки редослед - без повторување).

Во вториот ред е запишан бараниот број N (0 <= N <= 5000).

Излез

Излезот се состои од еден ред во кој треба да го отпечатите минималниот број на операции со кои може да се изрази бројот N. Секогаш ќе постои решение.

Во тест случаи кои носат најмалку 30% од поените, на калкулаторот ќе функционираат најмногу 4 цифри и резултатот (минималниот број на операции) ќе биде број помал или еднаков на 6.

Ограничувања

Временско ограничување: 3 seconds
Мемориско ограничување: 64 megabytes

Примери

влез
21
9

излез
7

влез
54
45

излез
2

влез
9871
5000

излез
5

Објаснување за првиот пример: еден можен израз е 1+2*2*2

Објаснување за третиот пример: еден можен израз е 99*99