問題文


(難易度目安:点)

自然数が与えられます。

このとき、あなたは以下の操作を任意回行うことができます。

を構成する各桁のうち、隣り合うつの数字のペアを選び、スワップする。

ただし、操作を終えたときの最上位の桁はであってはいけません。

(なお、操作の途中での最上位の桁がになっても良いものとします。)

自然数以上未満の自然数が与えられます。

を満たすために必要な最小の操作回数はいくつですか。

どのように操作を行っても不可能である場合はその旨を報告してください。

制約


・与えられるは最上位の桁がではない

出力


必要な最小の操作回数を行で出力してください。

ただし、どのように操作を行っても不可能である場合はを出力してください。

最後に改行してください。

入力


入力は以下の形式で与えられる。

N
M R

サンプル


入力1
201028
2 1
出力1
3

~ ~ ~ と操作するのが最適です。

操作回数は回です。

入力2
20000000
10 2
出力2
-1

でわった余りがであるためには、操作後にが最下位の桁に来る必要がありますが、これは操作後にの最上位がであってはいけないことに反します。よってこのようなことはありえず、を出力します。

入力3
123344533122341
24 8
出力3
4
入力4
390394632478555273
20 16
出力4
11

提出


Go (1.14)