One unknown hacker wants to get the admin's password of AtForces testing system, to get problems from the next contest. To achieve that, he sneaked into the administrator's office and stole a piece of paper with a list of $n$ passwords — strings, consists of small Latin letters.

Hacker went home and started preparing to hack AtForces. He found that the system contains only passwords from the stolen list and that the system determines the equivalence of the passwords $a$ and $b$ as follows:  two passwords $a$ and $b$ are equivalent if there is a letter, that exists in both $a$ and $b$;  two passwords $a$ and $b$ are equivalent if there is a password $c$ from the list, which is equivalent to both $a$ and $b$. 

If a password is set in the system and an equivalent one is applied to access the system, then the user is accessed into the system.

For example, if the list contain passwords "a", "b", "ab", "d", then passwords "a", "b", "ab" are equivalent to each other, but the password "d" is not equivalent to any other password from list. In other words, if:  admin's password is "b", then you can access to system by using any of this passwords: "a", "b", "ab";  admin's password is "d", then you can access to system by using only "d". 

Only one password from the list is the admin's password from the testing system. Help hacker to calculate the minimal number of passwords, required to guaranteed access to the system. Keep in mind that the hacker does not know which password is set in the system.


-----Input-----

The first line contain integer $n$ ($1 \le n \le 2 \cdot 10^5$) — number of passwords in the list. Next $n$ lines contains passwords from the list – non-empty strings $s_i$, with length at most $50$ letters. Some of the passwords may be equal.

It is guaranteed that the total length of all passwords does not exceed $10^6$ letters. All of them consist only of lowercase Latin letters.


-----Output-----

In a single line print the minimal number of passwords, the use of which will allow guaranteed to access the system.


-----Examples-----
Input
4
a
b
ab
d

Output
2
Input
3
ab
bc
abc

Output
1
Input
1
codeforces

Output
1


-----Note-----

In the second example hacker need to use any of the passwords to access the system.

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline

n = int(input())

def MakeSet(x):
     x.parent = x
     x.rank   = 0

def Union(x, y):
     xRoot = Find(x)
     yRoot = Find(y)
     if xRoot.rank > yRoot.rank:
         yRoot.parent = xRoot
     elif xRoot.rank < yRoot.rank:
         xRoot.parent = yRoot
     elif xRoot != yRoot:
         yRoot.parent = xRoot
         xRoot.rank = xRoot.rank + 1

def Find(x):
     if x.parent == x:
        return x
     else:
        x.parent = Find(x.parent)
        return x.parent

class Node:
    def __init__ (self, label):
        self.label = label
    def __str__(self):
        return self.label

used = [0] * 26
nodes = [Node(ch) for ch in range(26)]
[MakeSet(node) for node in nodes] 
  
for _ in range(n):
    s = input().strip()
    prev = -1
    for c in s:
        val = ord(c) - 97
        used[val] = 1
        if prev != -1:
            Union(nodes[prev], nodes[val])
        prev = val

outs = [0] * 26
for node in nodes:
    outs[Find(node).label] += 1

count = 0
for val in outs:
    if val != 0:
        count += 1

print(count + sum(used) - 26)
        


import sys
input = sys.stdin.readline

n = int(input())
p = list(range(n + 26))

def find(x):
    if x != p[x]:
        p[x] = find(p[x])
    return p[x]

for i in range(n):
    for c in set(input().rstrip()):
        p[find(ord(c) - 97)] = find(26 + i)

print(sum((p[x] == x) for x in range(26, n + 26)))


class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n
        self.cnt = n

    def root(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.parent[x] > self.parent[y]:
                x, y = y, x
            self.parent[x] += self.parent[y]
            self.parent[y] = x
            self.cnt -= 1

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def get_size(self, x):
        return -self.parent[self.root(x)]

    def get_cnt(self):
        return self.cnt

import sys
input = sys.stdin.readline

n = int(input())
s = [set(input()) for i in range(n)]

init_set = set([])
for i in range(n):
    s[i].remove('\n')
    init_set |= s[i]

uf = UnionFind(len(init_set))
to_int = {}
for i, char in enumerate(init_set):
    to_int[char] = i

for i in range(n):
    char1 = s[i].pop()
    for char in s[i]:
        a, b = to_int[char1], to_int[char]
        if not uf.is_same(a, b):
            uf.merge(a, b)
print(uf.get_cnt())

import sys
input = sys.stdin.readline

n=int(input())
#P=[input().strip() for i in range(n)]

Group = [i for i in range(26)] 
Nodes = [1]*(26) 
USE = [0]*26

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):
    if find(x) != find(y):
        if Nodes[find(x)] < Nodes[find(y)]:
            
            Nodes[find(y)] += Nodes[find(x)]
            Nodes[find(x)] = 0
            Group[find(x)] = find(y)
            
        else:
            Nodes[find(x)] += Nodes[find(y)]
            Nodes[find(y)] = 0
            Group[find(y)] = find(x)

for i in range(n):
    P=input().strip()

    for j in range(1,len(P)):
        Union(ord(P[j-1])-97,ord(P[j])-97)
    USE[ord(P[0])-97]=1

#print(USE)
#print(Group)

SET=set()
for i in range(26):
    if USE[i]==1:
        SET.add(find(i))

print(len(SET))
        



import sys
input = sys.stdin.readline

m = 26
uf = [-1]*m
def root(x):
    if uf[x] < 0:
        return x
    uf[x] = root(uf[x])
    return uf[x]
def unite(x,y):
    rx, ry = root(x), root(y)
    if rx == ry:
        return False
    if uf[rx] > uf[ry]:
        rx, ry = ry, rx
    uf[rx] += uf[ry]
    uf[ry] = rx
    return True

n = int(input())
used = [0]*m
for i in range(n):
    s = input()[:-1]
    s = list(set(ord(c)-ord("a") for c in s))
    l = len(s)
    for j in range(l):
        used[s[j]] = 1
        for k in range(j+1, l):
            unite(s[j], s[k])
ans = sum(uf[i]<0 and used[i] for i in range(m))
print(ans)

3

import os
import sys


def main():
    N = read_int()
    S = [inp() for _ in range(N)]
    print(solve(N, S))


class Node(object):
    def __init__(self, v):
        self.v = v
        self.p = self

    def union(self, other):
        r1 = self.find()
        r2 = other.find()
        if r1 is not r2:
            r1.p = r2

    def find(self):
        r = self
        while r.p != r:
            r = r.p
        n = self
        while n.p != n:
            p = n.p
            n.p = r
            n = p
        return r


def solve(N, S):
    letters = [None] * 26
    nodes = [Node(i) for i in range(N)]
    orda = ord('a')
    for i in range(N):
        s = S[i]
        b = [False] * 26
        for c in s:
            b[ord(c) - orda] = True
        for j in range(26):
            if b[j]:
                if letters[j] is None:
                    letters[j] = nodes[i]
                else:
                    nodes[i].union(letters[j])

    ns = set()
    for n in nodes:
        ns.add(n.find().v)
    return len(ns)


###############################################################################

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def __starting_point():
    main()

__starting_point()

class UnionFind(object):
    __slots__ = ['nodes']

    def __init__(self, n: int):
        self.nodes = [-1]*n

    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> bool:
        root_x, root_y, nodes = self.find(x), self.find(y), self.nodes

        if root_x != root_y:
            if nodes[root_x] > nodes[root_y]:
                root_x, root_y = root_y, root_x
            nodes[root_x] += nodes[root_y]
            nodes[root_y] = root_x

        return root_x != root_y


def __starting_point():
    import sys
    n = int(input())
    uf = UnionFind(26 + n)
    cc_a = ord('a')
    for i, p in enumerate((l.rstrip() for l in sys.stdin), start=26):
        for cc in list(map(lambda c: ord(c)-cc_a, set(p))):
            uf.unite(i, cc)

    ans = sum(1 for i in range(26, 26+n) if uf.nodes[i] < 0)
    print(ans)
__starting_point()

#!/usr/bin/env python3
import sys
input = sys.stdin.readline

class DisjointSet:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1] * n
        self.rank = [0] * n

    def root(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def has_same_root(self, x, y):
        return self.root(x) == self.root(y)

    def get_size(self, x):
        return self.size[self.root(x)]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

n = int(input())
password = []
DS = DisjointSet(26)
seen = set()
orda = ord("a")
for i in range(n):
    password = input().rstrip()
    if len(password) == 1:
        seen.add(password)
        continue
    for ch1, ch2 in zip(password, password[1:]):
        DS.unite(ord(ch1) - orda, ord(ch2) - orda)
        seen.add(ch1)
        seen.add(ch2)
pars = set()
for item in seen:
    pars.add(DS.root(ord(item) - orda))
print(len(pars))

import sys


def get(p, x):
    path_x = []
    while x != p[x]:
        path_x.append(x)
        x = p[x]
    return x, path_x
def join(p, rank, x, y):
    x, path_x = get(p, x)
    y, path_y = get(p, y)

    if x == y:
        return False
    else:
        if rank[x] > rank[y]:
            x, y = y, x
        if rank[x] == rank[y]:
            rank[y] += 1

        p[x] = y
        for el in path_x:
            p[el] = y
        for el in path_y:
            p[el] = y
        return True

def check(p, x, y):
    x, path_x = get(p, x)
    y, path_y = get(p, y)

    for el in path_x:
        p[el] = x
    for el in path_y:
        p[el] = y
    return x == y

def get_id(c):
    return ord(c) - 97

# inf = open('input.txt', 'r')
# reader = (line.rstrip() for line in inf)
reader = (s.rstrip() for s in sys.stdin)

n = int(next(reader))
p = list(range(26))
rank = [0] * 26
used = set()
for _ in range(n):
    word = next(reader)
    unq_cs = set(word)
    used.update(unq_cs)
    
    c1 = unq_cs.pop()
    i1 = get_id(c1)
    while unq_cs:
        c2 = unq_cs.pop()
        i2 = get_id(c2)
        join(p, rank, i1, i2)
        
unq_gr = set()
for c in used:
    gr_id, _ = get(p, get_id(c))
    unq_gr.add(gr_id)
print(len(unq_gr))

# inf.close()


n = int(input())
used = []
ekv = []
a = []
for i in range(n):
    s = list(input())
    a.append(s)
a.sort()

j = 1
t = 0
a.append("dsh")
r = 0
for i in range(n-1):
    r = 0
    for k in range(len(a[i])):
        if a[i][k] in a[i+1]:
            r = 1
            break
    if r == 0:
        j += 1

print(j)


import sys
input = sys.stdin.readline
 
def r1():
    return int(input())
def r2():
    return list(map(int, input().split()))

pred = {}
size = {}
k = 0

def get_lead(index):
    if pred[index] == index:
        return index
    pred[index] = get_lead(pred[index])
    return pred[index]

def merge(a, b, k):
    pred_a = get_lead(a)
    pred_b = get_lead(b)
    if pred_a == pred_b:
        return k
    k -= 1
    if size[pred_a] > size[pred_b]:
        pred_a, pred_b = pred_b, pred_a
    pred[pred_a] = pred_b
    size[pred_b] = max(size[pred_b], size[pred_a] + 1)
    return k

n = r1()
for i in range(n):
    psw = input()
    first = psw[0]
    for item in psw:
        if item == '\n':
            break
        if item not in pred:
            pred[item] = item
            size[item] = 1
            k += 1
        k = merge(item, first, k)
print(k)
    
    


# from sys import stdin
# def rl():
#     return [int(w) for w in stdin.readline().split()]
from bisect import bisect_right
from bisect import bisect_left
from collections import defaultdict
from math import sqrt,factorial,gcd,log2,inf,ceil
# map(int,input().split())
# # l = list(map(int,input().split()))
# from itertools import permutations
import sys
input = sys.stdin.readline

# t = int(input())
#
# for _ in range(t):
#     a,b,c = map(int,input().split())
#     a,b,c = sorted([a,b,c])
#     ans = 0
#     ans+=b
#     c-=b
#
#     a,c = sorted([a,c])
#     ans+=a
#     print(ans)


# print(ans)

def find_parent(u):
    if par[u]!=u:
        par[u]=find_parent(par[u])
    return par[u]




n = int(input())
la = []

hash = defaultdict(list)
par = [0]+[i+1 for i in range(26)]
rank = [1]*(26+1)
seti = set()
booli = [False]*(27)
for i in range(n):
       z = input()

       z = z[:len(z)-1]
       k = min(z)

       set1 = set(min(k))

       booli[ord(k) - 97 + 1] = True

       a = ord(k) - 97 + 1
       z2 = find_parent(a)
       for i in range(len(z)):
           booli[ord(z[i]) - 97 + 1] = True


           if z[i] not in set1 :

             b = ord(z[i]) - 97 + 1
             z1 = find_parent(b)
             if z1!=z2:
               par[z1] = z2

             set1.add(i)

ans = set()

for i in range(26):
        if booli[i+1] == True:
           # print(chr(i+98))
           z = find_parent(i+1)
           ans.add(z)

print(len(ans))





import sys
from itertools import combinations as cb
input = sys.stdin.readline


def f(u):
    if u != p[u]:p[u] = f(p[u])
    return p[u]

N = int(input())

p = [0] * 26
for i in range(26):
    p[i] = i

vst = set()

for i in range(N):
    t = input().rstrip()
    al = set()
    for a in t:
        k = ord(a) - 97
        al.add(k)
        vst.add(k)
    if len(al) > 1:
        for u,v in cb(al, 2):
            if f(u) != f(v):
                p[f(u)] = p[f(v)]

q = set()
for w in vst:
    q.add(p[f(w)])

print(len(q))


import sys
import string

def input():
    return sys.stdin.readline().strip()

def dfs(i,vis,al):
    vis[i] = True
    for j in al[i]:
        if not vis[j]:
            dfs(j,vis,al)

al = [list() for _ in range(26)]
got = set()
n = int(input())
for _ in range(n):
    s = input()
    s = set([ord(c)-ord('a') for c in s])
    s = list(s)
    for i in range(len(s)):
        got.add(s[i])
        for j in range(i+1,len(s)):
            al[s[i]].append(s[j])
            al[s[j]].append(s[i])
vis = [False]*26

cnt = 0
for i in range(26):
    if not vis[i] and i in got:
        #print(got)
        dfs(i,vis,al)
        cnt+=1
print(cnt)





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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x=None):
        if x is not None:
            return self.size[self.find(x)]
        else:
            res = set()
            for i in range(self.n+1):
                res.add(self.find(i))
            return len(res) - 1

N = INT()
A = [input() for i in range(N)]

S = set()
for a in A:
    for c in a:
        S.add(c)
tonum = {}
for i, c in enumerate(list(S)):
    tonum[c] = i

uf = UnionFind(len(tonum))
for a in A:
    for i, c in enumerate(a[1:], 1):
        x = tonum[a[i]]
        y = tonum[a[i-1]]
        if not uf.is_same(x, y):
            uf.union(x, y)
print(uf.get_size())


'''input
3
ab
bc
abc
'''
from sys import stdin, stdout


from collections import defaultdict, deque


def get_map(password):
	mymap  = defaultdict(list)

	for i in range(26):
		for j in range(len(password)):
			if chr(ord('a') + i) in password[j]:
				mymap[chr(ord('a') + i)].append(j)
	return mymap



def find_parent(node):
	t = node
	while parent[node] != node:
		node = parent[node]
	parent[t] = node
	return node

# main starts 
n = int(stdin.readline().strip())
password = []
parent = dict()
for _ in range(n):
	password.append(stdin.readline().strip())
	parent[_] = _ 

mymap = get_map(password)
for i in mymap:
	for j in range(1, len(mymap[i])):
		p1 = find_parent(mymap[i][j - 1])
		p2 = find_parent(mymap[i][j])	

		parent[p2] = p1

c = 0
for i in parent:
	if parent[i]  == i:
		c += 1

print(c)




"""
NTC here
"""
from sys import stdin

def iin(): return int(stdin.readline())
 
 
def lin(): return list(map(int, stdin.readline().split()))

class Disjoint_set:
    class node:
        def __init__(self, a):
            self.value = a
            self.p = self
            self.rank = 0

    def __init__(self, a):
        self.data = {i: self.make_set(i) for i in range(1,a+1)}

    def make_set(self, val):
        return self.node(val)

    def union(self, x, y):
        self.link(self.find_set(self.data[x]), self.find_set(self.data[y]))

    def link(self, val1, val2):
        if val1.rank > val2.rank:
            val2.p = val1
            val1.rank += 1
        else:
            val1.p = val2
            val2.rank += 1

    def find_set(self, val):
        if val.p.value != val.value:
            val.p = self.find_set(val.p)
        return val.p
    
    def solution(self):
        pr={}
        parent={}
        for i in self.data:
            vl=self.find_set(self.data[i]).value
            parent[i]=vl
            if vl in pr:
                pr[vl]+=1
            else:
                pr[vl]=1

        return pr



# range = xrange
# input = raw_input
# print("Case #{}: {} {}".format(i, n + m, n * m))

def main():
    n=iin()
    s=[''.join(list(set(input()))) for i in range(n)]
    adj=[[] for _ in range(26)]
    
    s=list(set(s))
    l=len(s)
    for k,i in enumerate(s):
        for j in i:
            adj[ord(j)-ord('a')].append(k+1)
    ds=Disjoint_set(l)
    #print(s, adj)
    done=set()
    for i in range(26):
        if adj[i]:
            x=adj[i][0]
            for j in adj[i]:
                if x!=j and (x,j) not in done and (j, x) not in done:
                    ds.union(x, j)
                    done.add((x, j))
    sl=ds.solution()
    print(len(sl))






    


        


     
main()


import sys
input=sys.stdin.readline
n=int(input())
def find(x):
    if x!=f[x]:
        f[x]=find(f[x])
    return f[x]
f=list(range(n+26))
for i in range(0,n):
	for j in set(input().rstrip()):
		f[find(ord(j)-97)]=find(i+26)
ans=0
for i in range(26,n+26):
	if f[i]==i:
		ans+=1
print(ans)

#!/usr/bin/env python3
import sys

#lines = stdin.readlines()
def rint():
    return list(map(int, sys.stdin.readline().split()))

def input():
    return sys.stdin.readline().rstrip('\n')

def oint():
    return int(input())

n = oint()

node = dict()
for _ in range(n):
    s = set(input())
    for c1 in s:
        if not c1 in node:
            node[c1] = s
        else:
            node[c1] = node[c1].union(s)
v = set()
def dfs(k):
    if k in v:
        return
    v.add(k)
    for kk in node[k]:
        if not kk in v:
            dfs(kk)
    return
ans = 0
for k in node:
    if k in v:
        continue
    ans += 1
    dfs(k)

print(ans)




from collections import *
from functools import reduce
import sys
input = sys.stdin.readline

def factors(n):    
    return set(reduce(list.__add__,([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

def li():return [int(i) for i in input().rstrip('\n').split(' ')]
def st():return input().rstrip('\n')
def val():return int(input())
l = []
for i in range(val()):
    l.append(st())
l.sort(key = lambda x:len(set(x)),reverse = 1)
d = {}
tot = len(l)
for i in l:
    curr = []
    do = 1
    for j in set(i):
        if j in d and do:
            tot -= 1
            do = 0
        curr.append(j)
    for j in curr:d[j] = 1
currans = tot
l.sort()
d = {}
tot = len(l)
for i in l:
    curr = []
    do = 1
    for j in set(i):
        if j in d and do:
            tot -= 1
            do = 0
        curr.append(j)
    for j in curr:d[j] = 1
print(min(currans,tot))


import sys
input=sys.stdin.readline
n=int(input())
f=[]
d=[]
for i in range(0,26):
	d.append([0]*26)
use=[0]*26
for i in range(0,26):
	f.append(i)
def find(x):
	if x!=f[x]:
		f[x]=find(f[x])
	return f[x]
for i in range(0,n):
	l=[]
	for j in set(input().rstrip()):
		use[ord(j)-97]=1
		l.append(ord(j)-97)
	ll=len(l)
	for k in range(0,ll):
		for j in range(k+1,ll):
			d[l[k]][l[j]]=1
for i in range(0,26):
	for j in range(0,26):
		if d[i][j]:
			if find(i)!=find(j):
				f[find(i)]=find(j)
ans=[]
a=0
for i in range(0,26):
	if use[i]==1 and find(i) not in ans:
		ans.append(find(i))
		a+=1
print(a)