AlgoLiga 2018

Jasio wie, że sekretny kod na którym mu zależy jest nieujemną całkowitą liczbą n cyfrową. Kłopot w tym, że poznał tylko niektóre jej cyfry. Teraz nie wie, czy ma tracić czas na próbowanie wszystkich możliwych kodów, czy też potrwa to za długo i powinien jeszcze dokładniej poznać tę liczbę.

Wejście

W pierwszej linii wejścia znajduje się liczba testów 0<t<=1000. Następnie każdy test w oddzielnej linii. Pojedynczy test składa się z liczby 0<n<=100 oraz, po spacji, ciągu n znaków z których każdy jest cyfrą, jeśli Jasio wie że w kodzie na danym miejscu stoi ta cyfra, lub znakiem zapytania, jeśli Jasio nie wie jaka cyfra stoi na danym miejscu w jego kodzie.

Wyjście

Dla każdego testu wynik w osobnej linii. Wynikiem jest liczba możliwych sekretnych kodów.

Przykład

Wejście:
2
3 12?
5 1?2?3

Wyjście:
10
100