Amanda has a string of lowercase letters that she wants to copy to a new string.  She can perform the following operations with the given costs. She can perform them any number of times to construct a new string $\boldsymbol{p}$:

Append a character to the end of string $\boldsymbol{p}$ at a cost of $\mbox{1}$ dollar. 
Choose any substring of $\boldsymbol{p}$ and append it to the end of $\boldsymbol{p}$ at no charge.

Given $n$ strings $s[i]$, find and print the minimum cost of copying each $s[i]$ to $p[i]$ on a new line.

For example, given a string $s=abcabc$, it can be copied for $3$ dollars.  Start by copying $\boldsymbol{a}$, $\boldsymbol{b}$ and $\textbf{c}$ individually at a cost of $\mbox{1}$ dollar per character.  String $p=abc$ at this time.  Copy $p[0:2]$ to the end of $\boldsymbol{p}$ at no cost to complete the copy.  

Function Description  

Complete the stringConstruction function in the editor below.  It should return the minimum cost of copying a string.  

stringConstruction has the following parameter(s):  

s: a string  

Input Format

The first line contains a single integer $n$, the number of strings. 

Each of the next $n$ lines contains a single string, $s[i]$.

Constraints

$1\leq n\leq5$  
$1\leq|s[i]|\leq10^5$  

Subtasks

$1\leq|s[i]|\leq10^3$ for $45\%$ of the maximum score.

Output Format

For each string $s[i]$ print the minimum cost of constructing a new string $p[i]$ on a new line.

Sample Input
2
abcd
abab

Sample Output
4
2

Explanation

Query 0: We start with $s=\text{"abcd''}$ and $p=\textsf{""}$.

Append character '$\mbox{a}$' to $\boldsymbol{p}$ at a cost of $\mbox{1}$ dollar, $p=\text{"a"}$. 
Append character '$\mbox{b}$' to $\boldsymbol{p}$ at a cost of $\mbox{1}$ dollar, $p=\text{"ab"}$. 
Append character '$\boldsymbol{\mathsf{c}}$' to $\boldsymbol{p}$ at a cost of $\mbox{1}$ dollar, $p=\text{"abc"}$. 
Append character '$\mbox{d}$' to $\boldsymbol{p}$ at a cost of $\mbox{1}$ dollar, $p=\text{"abcd"}$. 

Because the total cost of all operations is $1+1+1+1=4$ dollars, we print $4$ on a new line.

Query 1: We start with $s=\text{"abab''}$ and $p=\text{""}$.

Append character '$\mbox{a}$' to $\boldsymbol{p}$ at a cost of $\mbox{1}$ dollar, $p=\text{"a"}$. 
Append character '$\mbox{b}$' to $\boldsymbol{p}$ at a cost of $\mbox{1}$ dollar, $p=\text{"ab"}$. 
Append substring $\text{"ab''}$ to $\boldsymbol{p}$ at no cost, $p=\text{"abab''}$. 

Because the total cost of all operations is $1+1=2$ dollars, we print $2$ on a new line.

Note

A substring of a string $\mbox{S}$ is another string $S^{\prime}$ that occurs "in" $\mbox{S}$ (Wikipedia). For example, the substrings of the string "$\boldsymbol{abc}$" are "$\boldsymbol{a}$", "$\boldsymbol{b}$" ,"$\textbf{c}$", "$\boldsymbol{ab}$", "$\boldsymbol{bc}$", and "$\boldsymbol{abc}$".

Difficulty: EASY
Tags: String algorithms

Starter code:

Solutions:
t = int(input())
for i in range(t):
	s = input()
	print(len(set(s)))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	se = set()
	ans = 0
	for i in s:
		if i not in se:
			ans += 1
			se.add(i)
	print(ans)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(len(set(s)))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(len(set(s)))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(len(set(s)))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(len(set(s)))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	p = ''
	cost = 0
	for j in range(len(s)):
		if s[j] not in s[:j]:
			cost += 1
		p += s[j]
	print(cost)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	p = ''
	res = 0
	let = {}
	for i in s:
		if not i in let:
			let[i] = True
			res += 1
	print(res)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(len(set(list(s))))


T = int(input())
for cc in range(T):
	print(len(set(input())))


N = int(input())
for _ in range(N):
	S = input()
	C = set()
	cost = 0
	for c in S:
		if c not in C:
			cost += 1
			C.add(c)
	print(cost)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	count = 0
	p = {}
	for i in s:
		if p.get(i):
			continue
		else:
			p[i] = 1
			count += 1
	print(count)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	d = [0] * 26
	for c in s:
		d[ord(c) - ord('a')] = 1
	print(sum(d))


import sys

def solve(x):
	p = ''
	cost = 0
	for i in x:
		if i not in p:
			p = p + i
			cost = cost + 1
	return cost
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(solve(s))


n = int(input())
while n != 0:
	n -= 1
	s = input()
	print(len(set(s)))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	p = ''
	cost = 0
	for letter in s:
		if letter not in p:
			cost += 1
		p += letter
	print(cost)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(len(list(set(s))))


import sys
n = int(input().strip())
for a0 in range(n):
	dollars = 0
	s = input().strip()
	strings = set()
	for a in range(len(s)):
		if s[a] not in s[:a]:
			dollars += 1
	print(dollars)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	p = set()
	cost = 0
	for c in s:
		if c in p:
			pass
		else:
			p.add(c)
			cost += 1
	print(cost)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	dic = {s[0]: None}
	cost = 1
	n = len(s)
	j = 1
	while j < n:
		if s[j] in dic:
			cost = cost
		else:
			cost += 1
			dic[s[j]] = None
		j += 1
	print(cost)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	total = 0
	chars_in_p = set()
	for c in s:
		if c not in chars_in_p:
			total += 1
			chars_in_p.add(c)
	print(total)


n = int(input())
for i in range(n):
	s = input()
	p = ''
	cost = 0
	for j in s:
		if j in p:
			p += j
		else:
			p += j
			cost += 1
	print(cost)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	temp = set()
	count = 0
	for i in s:
		if i not in temp:
			temp.add(i)
			count += 1
	print(count)


import sys
n = int(input().strip())
for a0 in range(n):
	ans = ''
	cost = 0
	s = input().strip()
	for (i, c) in enumerate(s):
		if s[i:] in ans:
			ans += s[i:]
			break
		if c not in ans:
			ans += c
			cost += 1
	print(cost)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	dict_numbers = {}
	for i in range(len(s)):
		number = s[i]
		if not number in dict_numbers:
			dict_numbers[number] = 1
	print(len(dict_numbers))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	array = []
	cost = 0
	for i in s:
		if i not in array:
			array.append(i)
			cost += 1
	print(cost)


import sys

def calculate_price(s):
	price = 0
	p = []
	for c in s:
		if c in p:
			continue
		p.append(c)
		price += 1
	return price
n = int(input().strip())
for i in range(n):
	s = input().strip()
	price = calculate_price(s)
	print(price)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	seen = set()
	ret = 0
	for x in s:
		if x not in seen:
			ret += 1
			seen.add(x)
	print(ret)


num_strings = int(input().strip())
for each_case in range(num_strings):
	index = 0
	letters = set()
	word = input().strip()
	for i in range(len(word)):
		if word[i] not in letters:
			letters.add(word[i])
			if len(letters) == 26:
				break
	print(len(letters))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	d = dict()
	ans = 0
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
			ans += 1
	print(ans)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	Set = set()
	res = 0
	for c in s:
		if c not in Set:
			Set.add(c)
			res += 1
	print(res)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	p = ''
	cost = 0
	for k in s:
		if k in p:
			pass
		else:
			cost = cost + 1
			p = p + k
	print(cost)


import sys
n = int(input().strip())
for a0 in range(0, n):
	s = input().strip()
	c = 0
	temp = []
	for x in s:
		if x not in temp:
			c = c + 1
			temp.append(x)
	print(c)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	knownLetters = []
	for el in s:
		if not el in knownLetters:
			knownLetters.append(el)
	print(len(knownLetters))


import sys
n = int(input().strip())
for a0 in range(n):
	result = 0
	chars = set()
	for c in input():
		if not c in chars:
			result += 1
			chars.add(c)
	print(result)


import sys
cost = {}
n = int(input().strip())
for a0 in range(n):
	p = ''
	s = input().strip()
	for each in s:
		if each in p:
			p = p + each
		else:
			try:
				cost[a0] += 1
			except KeyError:
				cost[a0] = 1
			p = p + each
for each in cost:
	print(cost[each])


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	cost = 0
	p = ''
	for ch in s:
		if ch not in p:
			cost += 1
		p += ch
	print(cost)


import sys
n = int(input().strip())
for a0 in range(n):
	p = ''
	cost = 0
	s = input().strip()
	chars = list(s)
	for char in chars:
		if char not in p:
			cost += 1
		p += char
	print(cost)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	l = []
	c = 0
	for i in s:
		if i not in l:
			c = c + 1
		if l == []:
			l.append(i)
		else:
			l.append(l[-1] + i)
			l.append(i)
	print(c)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(len(set(s)))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	charsForP = {}
	cost = 0
	for i in range(len(s)):
		if s[i] not in charsForP:
			charsForP[s[i]] = 1
			cost += 1
	print(cost)


import sys
n = int(input().strip())
for a0 in range(n):
	k = []
	c = 0
	s = str(input())
	for i in range(0, len(s)):
		if s[i] not in k:
			k.append(s[i])
			c += 1
	print(c)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	used = set(s)
	print(len(used))


import string
n = int(input())
for _ in range(n):
	s = input()
	print(sum([c in s for c in string.ascii_lowercase]))


for _ in range(int(input())):
	print(len(set(input())))


n = int(input())
for i in range(n):
	s = input().strip()
	seen = set()
	for c in s:
		seen.add(c)
	print(len(seen))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	p = set(s)
	print(len(p))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	d = {}
	p = ''
	c = 0
	for i in s:
		if i not in d:
			p += i
			d[i] = 1
			c += 1
		else:
			pass
	print(c)


import sys
n = int(input().strip())
for i in range(n):
	p = ''
	count = 0
	s = input().strip()
	for i in s:
		if i not in p:
			p += i
			count += 1
	print(count)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(len(list(set([i for i in s]))))


import sys
n = int(input().strip())
for a0 in range(n):
	s = list(input().strip())
	print(len(list(set(s))))


import sys
words = []
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	words.append(s)
costs = []
for word in words:
	cost_counter = 0
	p = ''
	for letter in word:
		if letter not in p:
			p += letter
			cost_counter += 1
		else:
			p += letter
	costs.append(cost_counter)
for cost in costs:
	print(cost)


import sys

def p_cost(s):
	unique_letters = {}
	for letter in s:
		unique_letters[letter] = 0
	return len(unique_letters)
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(p_cost(s))


import sys
n = int(input().strip())
for a0 in range(n):
	count = 0
	s = input().strip()
	for i in range(len(s)):
		if s[i] not in s[:i]:
			count += 1
	print(count)


import sys
c = 0
n = int(input().strip())
for a0 in range(n):
	s = ''.join(set(input().strip()))
	print(len(s))


import sys
Q = int(input().strip())
for a0 in range(Q):
	S = input().strip()
	m = len(S)
	Sprev = [None] * m
	Dprev = {}
	for (i, c) in enumerate(S):
		Sprev[i] = Dprev.get(c)
		Dprev[c] = i
	cost = 0
	for p in range(m):
		if Sprev[p] is None:
			cost += 1
	print(cost)


for _ in range(int(input())):
	s = input()
	print(len(set(s)))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(len(set(s)))


import sys
n = int(input().strip())
for a0 in range(n):
	s = set(input().strip())
	print(len(s))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(len(set(s)))


import sys
n = int(input().strip())
for a0 in range(n):
	print(str(len(set(list(input().strip())))))


import sys
n = int(input().strip())
for a0 in range(0, n, 1):
	s = input().strip()
	letters_Set = set()
	overall_Cost = 0
	for l in s:
		if l in letters_Set:
			pass
		else:
			letters_Set.add(l)
			overall_Cost += 1
	print(overall_Cost)


t = int(input())
for T in range(t):
	a = input()
	z = list(set(list(a)))
	print(len(z))


def distinctChars(string):
	return len(set(list(string)))
n = int(input())
for i in range(n):
	print(distinctChars(input().strip()))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	p = ''
	cost = 0
	for char in s:
		if char in p:
			p += char
		else:
			p += char
			cost += 1
	print(cost)


import sys

def to_pay(s):
	paid_letters = []
	paid = 0
	for letter in s:
		if letter not in paid_letters:
			paid += 1
			paid_letters.append(letter)
	return paid
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(to_pay(s))


import sys
n = int(input().strip())
for a in range(n):
	s = input().strip()
	pos = 0
	letters = 0
	for l in s:
		if not l in s[0:pos]:
			letters += 1
		pos += 1
	print(letters)


n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	p = []
	count = 0
	for i in s:
		if i not in p:
			count += 1
			p.append(i)
	print(count)


import sys
import collections
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	ret = len(collections.Counter(s))
	print(ret)


import sys
n = int(input().strip())
for i in range(n):
	s = input().strip()
	p = ''
	cost = 0
	for char in s:
		if char in p:
			p += char
		else:
			p += char
			cost += 1
	print(cost)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	cnt = 1
	pIdx = 1
	seen = set([s[0]])
	while pIdx < len(s):
		if s[pIdx] not in seen:
			cnt += 1
		seen.add(s[pIdx])
		pIdx += 1
	print(cnt)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	letters = set()
	cost = 0
	for ch in s:
		if not ch in letters:
			letters.add(ch)
			cost += 1
	print(cost)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	s = ''.join(set(s))
	print(len(s))


for word in [input() for _ in range(int(input()))]:
	print(len(set(word)))


n = int(input().strip())
for case in range(n):
	word = input().strip()
	letters = set(word)
	print(len(letters))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(len(set(s)))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	substrings = []
	print(len(set(s)))


import sys
n = int(input().strip())
for _ in range(n):
	s = str(input().strip())
	Dict = {}
	for element in s:
		Dict[element] = True
	ans = 0
	for (k, v) in Dict.items():
		if Dict[k]:
			ans += 1
	print(ans)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(len(set(s)))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(len(set(s)))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	cost = 0
	p = ''
	for c in s:
		if p.find(c) == -1:
			cost = cost + 1
		p = p + c
	print(cost)


import sys
n = int(input().strip())
for a0 in range(n):
	text = input().strip()
	cost = 0
	result = ''
	for c in text:
		if not c in result:
			cost += 1
		result += c
	print(cost)


import sys
from collections import Counter
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	data = Counter(s)
	out = 0
	for i in data:
		out += 1
	print(out)


import sys
n = int(input().strip())
for a0 in range(n):
	count = 0
	newWord = []
	s = input().strip()
	newS = list(s)
	for let in newS:
		if let in newWord:
			count = count
		else:
			newWord.append(let)
			count = count + 1
	print(count)


from collections import deque

def cost(word):
	letters = set(word)
	letter_count = len(set(letters))
	return letter_count
	costs = {}
	q = deque()
	for letter in letters:
		costs[letter] = 1
		q.append(letter)
	while q:
		p_candidate = q.popleft()
		length = len(p_candidate)
		for i in range(length * 2, length, -1):
			if word[length:i] in p_candidate:
				new_p_candidate = p_candidate + word[length:i]
				costs[new_p_candidate] = costs[p_candidate]
				if new_p_candidate == word or len(set(new_p_candidate)) == len(set(letters)):
					return costs[new_p_candidate]
				q.append(new_p_candidate)
				break
		new_p_candidate = word[0:length + 1]
		if new_p_candidate not in costs:
			costs[new_p_candidate] = costs[p_candidate] + 1
			q.append(new_p_candidate)
		if new_p_candidate == word or len(set(new_p_candidate)) == letter_count:
			return costs[new_p_candidate]
n = int(input())
words = (input() for _ in range(n))
for word in words:
	print(cost(word))


import sys
n = int(input().strip())
p = set()
cost = 0
for a0 in range(n):
	s = input().strip()
	for letter in s:
		if letter not in p:
			p.add(letter)
			cost += 1
		else:
			p.add(letter)
	print(cost)
	cost = 0
	p.clear()


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	p = ''
	letters = [0] * 26
	alfabeto = 'abcdefghijklmnopqrstuvwxyz'
	cost = 0
	for char in s:
		if not letters[alfabeto.index(char)]:
			cost += 1
			letters[alfabeto.index(char)] = 1
	print(cost)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	p = []
	cost = 0
	for item in s:
		if item not in p:
			cost = cost + 1
		p.append(item)
	print(cost)


N = int(input())
words = []
for i in range(N):
	words.append(input())
for word in words:
	result = set()
	for s in word:
		result.add(s)
	print(len(result))


n = int(input())
for i in range(0, n):
	s = input()
	string = s[0]
	cost = 1
	for i in range(1, len(s)):
		if s[i] in string:
			string = string + s[i]
		else:
			string = string + s[i]
			cost = cost + 1
	print(cost)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	seen = set([])
	count = 0
	for i in s:
		if i not in seen:
			count += 1
			seen.add(i)
	print(count)


for _ in range(int(input())):
	print(len(set(input())))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	p = ''
	t = 0
	for c in s:
		if c in p:
			p += c
		else:
			p += c
			t += 1
	print(t)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	p_set = set()
	for c in s:
		p_set.add(c)
	print(len(p_set))


import sys
import collections
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(len(collections.Counter(s)))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	letters = []
	for i in s:
		if not i in letters:
			letters.append(i)
	print(len(letters))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(len(set(s)))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	b = ''.join(set(s))
	print(len(b))


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	cost = len(set(s))
	print(cost)


import sys
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	p = []
	t = 0
	for c in s:
		if c not in p:
			p.append(c)
			t += 1
	print(t)