SPOJ in Armenian

Տրված է n երկարությամբ թվանշաններից և ՛?՛-ներից կազմված տող. Պետք է ՛?՛- ները փոխարինել թվանշաններով այնպես, որ ստացված թիվը բաժանվի տրված k-ի վրա և լինի մինիմալ, իսկ եթե չկա այդպիսի թիվ՝ տպել -1։

Մուտքային տվյալներ

Առաջին տողում տրված է t (1 ≤ t ≤ 10) թիվը թեստերի քանակը:

Ամեն թեստի համար տրված են n և k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 2) բնական թվերը, որտեղ n-ը տրված թվի թվանշանների քանակն է և n երկարությամբ տող կազմված ? նշաններից և թվանշաններից:

Ելքային տվյալներ

Տպել այն մինիմալ թիվը, որը բավարարում է վերը նշված պայմաններին և մինիմալն է, իսկ եթե չկա այդպիսի թիվ՝ տպել -1:

Օրինակ

Մուտք.
2
2 1
4?
2 2
?3

ելք.
40
-1