Polycarpus takes part in the "Field of Wonders" TV show. The participants of the show have to guess a hidden word as fast as possible. Initially all the letters of the word are hidden.

The game consists of several turns. At each turn the participant tells a letter and the TV show host responds if there is such letter in the word or not. If there is such letter then the host reveals all such letters. For example, if the hidden word is "abacaba" and the player tells the letter "a", the host will reveal letters at all positions, occupied by "a": 1, 3, 5 and 7 (positions are numbered from left to right starting from 1).

Polycarpus knows m words of exactly the same length as the hidden word. The hidden word is also known to him and appears as one of these m words.

At current moment a number of turns have already been made and some letters (possibly zero) of the hidden word are already revealed. Previously Polycarp has told exactly the letters which are currently revealed.

It is Polycarpus' turn. He wants to tell a letter in such a way, that the TV show host will assuredly reveal at least one more letter. Polycarpus cannot tell the letters, which are already revealed.

Your task is to help Polycarpus and find out the number of letters he can tell so that the show host will assuredly reveal at least one of the remaining letters.


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 50) — the length of the hidden word.

The following line describes already revealed letters. It contains the string of length n, which consists of lowercase Latin letters and symbols "*". If there is a letter at some position, then this letter was already revealed. If the position contains symbol "*", then the letter at this position has not been revealed yet. It is guaranteed, that at least one letter is still closed.

The third line contains an integer m (1 ≤ m ≤ 1000) — the number of words of length n, which Polycarpus knows. The following m lines contain the words themselves — n-letter strings of lowercase Latin letters. All words are distinct.

It is guaranteed that the hidden word appears as one of the given m words. Before the current move Polycarp has told exactly the letters which are currently revealed.


-----Output-----

Output the single integer — the number of letters Polycarpus can tell so that the TV show host definitely reveals at least one more letter. It is possible that this number is zero.


-----Examples-----
Input
4
a**d
2
abcd
acbd

Output
2

Input
5
lo*er
2
lover
loser

Output
0

Input
3
a*a
2
aaa
aba

Output
1



-----Note-----

In the first example Polycarpus can tell letters "b" and "c", which assuredly will be revealed.

The second example contains no letters which can be told as it is not clear, which of the letters "v" or "s" is located at the third position of the hidden word.

In the third example Polycarpus exactly knows that the hidden word is "aba", because in case it was "aaa", then the second letter "a" would have already been revealed in one of previous turns.

Difficulty: competition

Starter code:

Solutions:
N = int(input())
p = input()
M = int(input())
words = [input() for _ in range(M)]
cnt = 0
letters = [set() for _ in range(M)]
used = set()
for c in p:
    used.add(c)
fail = [False]*M

for i, w in enumerate(words):
    for j, c in enumerate(w):
        if p[j] == '*':
            letters[i].add(c)
            if c in used:
                fail[i] = True
        elif p[j] != c:
            fail[i] = True

for i in range(26):
    ch = chr(ord('a') + i)
    ok = True
    for i, s in enumerate(letters):
        ok = ok and (ch in s or fail[i])
    if ok: cnt += 1
print(cnt)


from string import ascii_lowercase as lower

char = int(input())

s = input()
new = [input() for k in range(int(input()))]

used = set()
can_be_said = set(lower)
indices = []
others = []

for index in range(char):
    if s[index] != '*':
        used.add(s[index])
        others.append(index)
    else:
        indices.append(index)

for word in new:
    now = set()
    
    for i in indices:
        now.add(word[i])

    is_ = True
    for i in others:
        if (s[i] != word[i]):
            is_ = False
    if not is_:
        continue
        
    if len(now.intersection(used)) == 0:
        can_be_said = can_be_said.intersection(now)

can_be_said = can_be_said - used
print(len(can_be_said))


import math
import re
import string


def ria():
    return [int(i) for i in input().split()]


def ri():
    return int(input())


def rfa():
    return [float(i) for i in input().split()]


eps = 1e-9


def is_equal(a, b):
    return abs(a - b) <= eps


def distance(p0, p1):
    return math.sqrt((p0[0] - p1[0]) ** 2 + (p0[1] - p1[1]) ** 2)


N = ri()
hid = input()
mpk = {}
totalKek = 0
for n, i in enumerate(string.ascii_lowercase):
    mpk[i] = 1 << n
    totalKek |= mpk[i]

M = ri()
revealed = 0
for i in hid:
    if i != '*':
        revealed |= mpk[i]
isAny = False

for i in range(M):
    t = input()
    isAny=True
    bad = False
    hidBit = 0

    for n, j in enumerate(t):
        if hid[n] != '*':
            if hid[n] != t[n]:
                bad = True
            continue


        hidBit |= mpk[j]
    if hidBit & revealed != 0 or bad:
        continue
    totalKek &= hidBit

if isAny:
    print(str(bin(totalKek)).count('1'))
else:
    exit(-1)

n = int(input())
s = input()

lr = []
r = []
w = set()
for i in range(len(s)):
	if s[i] == '*':
		lr.append(i)
	else:
		r.append(i)
		w.add(s[i])
m = int(input())

k = None
for i in range(m):
	e = input()
	f = False
	for j in lr:
		if e[j] in w:
			f = True
			break
	for j in r:
		if e[j] != s[j]:
			f = True
			break
	if f:
		continue
	if k is None:
		k = set(e[i] for i in lr)
	else:
		u = set(e[i] for i in lr)
		k = k.intersection(u)

print(len(k))

n = int(input())
s = input()
a = []
m = int(input())
for i in range(m):
    line = input()
    st = set()
    flag = False # 无效
    for i in range(n):
        if s[i] == '*':
            st.add(line[i])
        elif s[i] != line[i]:
            flag = True
    for i in range(n):
        if s[i] in st:
            flag = True
            break
    if flag:
        continue
    if len(st) > 0:
        a.append(st)
x = [0 for i in range(30)]
for e in a:
    for t in e:
        x[ord(t) - ord('a')] += 1
ans = 0
for i in range(30):
    if x[i] == len(a):
        ans += 1
print(ans)
#print(x)
#print(a)


n=int(input())
s=input().strip()
m=int(input())
l=[]
l1=[]
lmain=[]
for i in range(26):
    l.append(0)
    lmain.append(0)
for i in s:
    if (i!='*'):
        lmain[ord(i)-97]=1
for i in range(m):
    s1=input().strip()
    f=0
    for j in range(n):
        if (s[j]=='*' and lmain[ord(s1[j])-97]==1):
            f=1
            break
        elif (s[j]!='*'):
            if (s1[j]!=s[j]):
                f=1
                break
    if (f==0):
        l1.append(s1)
length=len(l1)
for i in range(length):
    l2=[]
    s1=l1[i]
    for j in range(26):
        l2.append(0)
    for j in range(n):
        if (s[j]=='*'):
            if (l2[ord(s1[j])-97]!=1):
                l[ord(s1[j])-97]+=1
                l2[ord(s1[j])-97]=1
print(l.count(length))


n = int(input())
s = input()

mp = dict()
st = [0]*n
k = 0
for i in s:
	if i.isalpha()==True:
		mp[i] = -1
	else:
		st[k] = 1
	k+=1

q = int(input())
tp = q
for i in range(q):
	s2 = input()
	cns = 0
	flag = 1
	for i in range(n):
		if s[i]!=s2[i] and not st[i]:
			tp-=1
			flag = 0
			break
		elif s2[i] in list(mp.keys()) and mp[s2[i]]==-1 and st[i]:
			tp-=1
			flag = 0
			break
	if flag :
		az = [0]*26
		for i in range(n):
			if s2[i] not in list(mp.keys()):
				mp[s2[i]]=1
				az[ord(s2[i])-97] = 1
			elif mp[s2[i]]!=-1 and not az[ord(s2[i])-97]:
				mp[s2[i]]+=1
				az[ord(s2[i])-97] = 1
cns = 0

for i in list(mp.keys()):
  if mp[i]==tp:
    cns+=1
print(cns)


n = int(input())
S = input()
HaveLetters = set(list(S))
m = int(input())
words = []
CanLetters = set([chr(i) for i in range(ord("a"), ord("z") + 1)]) - HaveLetters
for _ in range(m):
    Word = input()
    for i in range(n):
        if S[i] == "*":
            if Word[i] in HaveLetters:
                break
        else:
            if Word[i] != S[i]:
                break
    else:
        words += [Word]
ans = 0
for letter in CanLetters:
    can = True
    for Word in words:
        if letter not in Word:
            can = False
            break
    if can:
        ans += 1
print(ans)



import string
input() # ignore length of word
already_revealed = input()

n = int(input())

indeces = [i for i, x in enumerate(already_revealed) if x == "*"]
revealed_letters = set(already_revealed)

end_set = set(string.ascii_lowercase + "%")
for i in range(n):
  word = input()
  
  #check word
  word_ok = True
  for i, char in enumerate(word):
    if i not in indeces:
      if already_revealed[i] != char:
        word_ok = False
        
  if not word_ok:
    continue
  
  possible_letters = set(word[index] for index in indeces)
  if len(possible_letters.intersection(revealed_letters)) > 0:
    continue
  
  end_set = possible_letters.intersection(end_set)

if len(end_set) == 27:
  print(0)
else:
  print(len(end_set))

n=int(input())
s=input()
e=set()
nbret=0
for x in s:
    if x=='*':
        nbret+=1
    else:
        e.add(x)
m=int(input())

mini=nbret
L=[]
for i in range(m):
    e1=set()
    s1=input()
    for k,x in enumerate(s1):
        if s[k]!="*" and x!=s[k]:
            e1.clear()
            break
        if s[k]=='*' and x in e:
            e1.clear()
            break
        if s[k]=='*' and x not in e:
            e1.add(x)
    if len(e1)>0:
        L.append(e1)
e=L[0]
maxi=len(e)
for i in range(1,len(L)):
    if len(L[i])>maxi:
        maxi=len(L[i])
    e=e & L[i]

print(len(e))

#if len(e)==0:
#    if m==2:
#        print(maxi)
#else:
#    print(len(e))
        
#if len(e)>0 and len(e)<=nbret:

#else:
 #   print(0)


#while True:
n = int(input())
mark = [0]*26
notinclude = [0]*10001
s = input()
t = int(input()) 
data = [ input() for _ in range(t)]
for i in s:
    if i != '*':
        mark[ord(i)-97]=1
sets = {}
for j in range(t):
    sets[j]=set()
    for i in range(n):
        if s[i]=='*':
            if mark[ord(data[j][i])-97]==0:
                sets[j].add(data[j][i])
            else:
                notinclude[j]=1
        elif s[i]!=data[j][i]:
            notinclude[j]=1
            
ans=set(['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'])
temp=0
#print(sets)
for i in sets:
    if len(sets[i]) and notinclude[i]==0:
        temp=1
        ans = ans&sets[i]
#print(ans)
print(0 if temp==0 else len(ans))

''' input
2
**
3
ba
ba
ba

'''


n=int(input())
s=list(input())
dis=[]
ind=[]
ii=[]
for i in range(n):
    if(s[i]!='*'):
        dis.append(s[i])
        ii.append(i)
    else:
        ind.append(i)
di=set(dis)
c=[]
m=int(input())
for i in range(m):
    t=list(input())
    dp=0
    for j in ii:
        if(t[j]!=s[j]):
            dp=1
            break
    if(dp==0):
        q=[]
        for j in ind:
            q.append(t[j])
        q=set(q)
        oo=len(q)
        q=q-di
        ooo=len(q)
        if(len(q)!=0 and oo==ooo):
            c.append(q)

if(len(c)==0):
    print(0)
else:
    ss=c[0]
    l=len(c)
    for i in range(1,l):
        ss=ss.intersection(c[i])
    print(len(ss))

n = int(input())
word = input()

ast = word.count('*')
mas = [i for i in range(n) if word[i] == '*']
mas1 = [i for i in range(n) if word[i] != '*']
st = [word[i] for i in range(n) if word[i] != '*']

m = int(input())
Mas = list()
for i in range(m):
    temp = input()
    f = True
    for j in mas1:
        if temp[j] != word[j]:
            f = False
            break
    if f:
        t = [temp[k] for k in mas if temp[k] not in st]
        if len(t) == ast:
            Mas.append(set(t))

ans = set()
for el in Mas:
    ans |= el

count = 0
for i in ans:
    f = True
    for j in Mas:
        if i not in j:
            f = False
            break
    if f:
        count += 1

print(count)


n = int(input())
s = input()
m = int(input())
l = []
cnt_ = []
cnt = []
for i in range(n):
	if s[i]=='*':
		cnt_.append(i)
	else: cnt.append(i)
for x in range(m):
	flag = True
	st = input()
	for j in cnt_:
		if st[j] in s:
			flag = False
	else:
		for j in cnt:
			if st[j]!=s[j]: flag =False
	if flag:
		l.append(st)
g = [[] for i in range(len(l))]
for i in range(len(l)):
	for j in cnt_:
		g[i].append(l[i][j])
for i in range(len(g)):
	g[i] = list(set(g[i]))
ans = 0
for ch in g[0]:
	for li in g:
		if ch not in li: break
	else: ans = ans+1
print(ans)

n = int(input())
word = input()

ast = word.count('*')
mas = [i for i in range(n) if word[i] == '*']
mas1 = [i for i in range(n) if word[i] != '*']
st = {word[i] for i in mas1}

m = int(input())
Mas = list()
for i in range(m):
    temp = input()
    f = True
    for j in mas1:
        if temp[j] != word[j]:
            f = False
            break
    if f:
        t = [temp[k] for k in mas if temp[k] not in st]
        if len(t) == ast:
            Mas.append(set(t))

ans = set()
for el in Mas:
    ans |= el

count = 0
for i in ans:
    f = True
    for j in Mas:
        if i not in j and len(j) > 0:
            f = False
            break
    if f:
        count += 1

print(count)


#python 3.5.2

n = int(input())
kataawal = input()

pos = []
posmuncul = []
muncul = set()
for i,x in zip(range(n),kataawal):
    if (x == '*'):
        pos.append(i)
    else:
        muncul.add(x)
        posmuncul.append(i)

m = int(input())
belum = []
for i in range(m):
    kata = input()
    yay = set()
    cancel = False
    for x in posmuncul:
        if (kata[x] != kataawal[x]):
            cancel = True
            break
            
    if (not cancel):
        for x in pos:
            if (kata[x] in muncul):
                cancel = True
                break
            else:
                yay.add(kata[x])

        if (not cancel):
            belum.append(yay)

if (len(belum) > 1):
    hoo = belum[0]
    for sett in belum[1:]:
        hoo = hoo.intersection(sett)
    print(len(hoo))
elif(len(belum) == 0):
    print(0)
else:
    print(len(belum[0]))

import string
m = int(input())
word = input()
words = set()
stars = set()
let = {a for a in string.ascii_lowercase}
for i in range(0, len(word)):
    if word[i] == '*':
        stars.add(i)
    else:
        words.add(word[i])

n = int(input())
tse = set()
for i in range(0, n):
    st = input()
    for j in stars:
        tse.add(st[j])
    flag = True
    j = 0
    while j < m and (st[j] == word[j] or j in stars):
        j += 1

    if len(tse.intersection(words)) != 0 or j != m:
        tse.clear()
        continue
    let = let.intersection(tse)
    tse.clear()

if len(stars) == 0:
    print(0)
else:
    print(len(let))


from collections import defaultdict

def get_revealed(hid):
	revealed = set()
	for ch in hid:
		if ch!='*':
			revealed.add(ch)
	return revealed

def test_already_shown(s1,s2):
	for i in range(len(s1)):
		if s1[i]!='*' and s1[i]!=s2[i]:
			return False
	return True

def check_revealed_present(s1,s2,revealed):
	for i in range(len(s1)):
		if s1[i]=='*':
			if s2[i]  in revealed:
				return False
	return True

def process(s1,s2,d):
	temp = set()
	for i in range(len(s1)):
		if s1[i]=='*':
			temp.add(s2[i])
	for i in temp:
		if i not in d:
			d[i] = 1
		else:
			d[i]+=1
	return d


n = int(input())
hid = input()
revealed = get_revealed(hid)
#print(revealed)
m = int(input())
x = 0
d = {}
for i in range(m):
	s = input()
	if not test_already_shown(hid,s):
		continue
	if not check_revealed_present(hid,s,revealed):
		continue
	d = process(hid,s,d)
	#print("sad")
	x+=1
ans = 0
#print(x,revealed,d)
for i in d:
	if d[i]==x:
		ans+=1
print(ans)







# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

"""
created by shhuan at 2017/10/22 17:36

"""

N = int(input())
W = input()
M = int(input())

words = set()
for i in range(M):
    words.add(input())

revealed = set(W) - {'*'}
idx = [i for i, w in enumerate(W) if w == '*']
badwords = set()
guesses = set()

for i in idx:
    for u in words:
        if u[i] in revealed:
            badwords.add(u)

for i, w in enumerate(W):
    if w != '*':
        for u in words:
            if u[i] != w:
                badwords.add(u)


words -= badwords

for i in idx:
    w = W[i]
    for u in words:
        c = u[i]
        guesses.add(c)

ans = 0
for g in guesses:
    left = {v for v in words}
    for i in idx:
        for w in {v for v in left}:
            if w[i] == g:
                left.remove(w)
    if not left:
        ans += 1

print(ans)

n=int(input())
s=input()
mask=0
isunknown=[0]*n
for i in range(n):
    if s[i] != '*':
        mask|=1<<(ord(s[i])-97)
    else:
        isunknown[i]=1
m=int(input())
ans = (1<<26)-1
for i in range(m):
    words=input()
    umask=0
    li=[]
    for j in range(n):
        if isunknown[j]:
            umask|=1<<(ord(words[j])-97)
            li.append('*')
        else:
            li.append(words[j])
    if umask&mask or s!=''.join(li): continue
    ans&=umask
realans=0
while ans:
    realans+=ans&1
    ans>>=1
print(realans)


c = input()
s = input()

star = []
no_star = []
for i in range(len(s)):
    if s[i] == '*':
        star.append(i)
    else:
        no_star.append(i)

n = int(input())
d = {}
skip = 0
for i in range(n):
    s1 = input()
    ext = 0
    for i in no_star:
        if s1[i] not in s:
            ext = 1
    for i in star:
        if s1[i] in s:
            ext = 1
            break
    if ext == 1:
        skip+=1
        continue
    mas = []
    for i in star:
        mas.append(s1[i])
    mas = list(set(mas))
    for i in mas:
        if i not in d:
            d[i] = 1
        else:
            d[i] += 1
ans = 0
for i in d:
    if d[i] == n-skip:
        ans+=1
print (ans)


n = int(input())
s = input()
already = set()
for i in s:
    if i != '*':
        already.add(i)
ans = [chr(ord('a') + i) for i in range(26)]
ans = set(ans)
for i in range(int(input())):
    cur = input()
    can = True
    clos = set() #should be closed
    for j in range(n):
        if s[j] == '*':
            clos.add(cur[j])
        elif s[j] != cur[j]:
            can = False
            break
    if can:
        if (already & clos) != set():
            can = False
    if can:
        ans = (ans & clos)
print(len(ans))


import string

n = int(input())
w = input()
let = set(filter(lambda x: x != '*', w))
ans = None
for _ in range(int(input())):
	v = input()
	check = True
	for c in let:
		check &= not [1 for a, b in zip(w, v) if (a == c) ^ (b == c)]
	if check:
		if ans is None:
			ans = set(v) - let
		ans &= set(v) - let
print(len(ans))

import string
n = int(input())
s = list(str(input()))
m = int(input())
l = []
result = 0
for i in range(m):
    l.append(list(str(input())))
#print(l)
index = []
have = []
for i in range(n):
    if s[i] == '*':
        index.append(i)
    else:
        have.append(s[i])
have = set(have)
#print(index)
#print(have)
t = [1 for i in range(m)]
c = len(index)
for i in range(m):
    for j in index:
        if (l[i])[j] in have:
            t[i] = 0
            break
for j in range(m):
    for i in range(n):
        if i not in index:
            if (l[j])[i] != s[i]:
                t[j] = 0
                break

new = []
for i in range(m):
    if t[i] == 1:
        new.append(l[i])
#print(new)

alph = list(string.ascii_lowercase)
for i in have:
    alph.remove(i)
ll = len(new)
for i in alph:
    count = 0
    for j in range(len(new)):
        for k in index:
            if (new[j])[k] == i:
                count += 1
                break
    if count == ll:
        result += 1
print(result)

l = int(input())
secret = input()
indexes = []
noLetters = []
alph = ""

for i in range(len(secret)):
	if secret[i] == "*":
		indexes.append(i)
	else:
		noLetters.append(secret[i])

n = int(input())
dico = []
for _ in range(n):
	word = input()
	s = ""
	ok = True
	for i in range(len(word)):
		if i in indexes and word[i] not in noLetters:
			s+=word[i]
		elif word[i] != secret[i]:
			ok = False
			break
	if ok and s != "" and s not in dico:
		dico.append(s)
		for c in s:
			if c not in alph:
				alph+=c

total = 0
for c in alph:
	ok = True
	for w in dico:
		if c not in w:
			ok = False
			break
	if ok:
		total+=1
print(total)