В этом году в Конохе вновь проводится экзамен на звание Чунина, и в нем участвуют \(n\) ниндзя с именами \(s_1\), \(s_2\), ..., \(s_n\). Все имена участников различны. Один из этапов экзамена — сражения между участниками. В этом году руководство Конохи решило, что определять, кто с кем сражается, будут по-новому. Ниндзя \(i\) сражается с ниндзя \(j\), если выполнены три правила:
- \(i \neq j\);
- \(s_{j}\) — подстрока \(s_{i}\);
- не существует \(k\), отличного от \(i\) и \(j\) такого, что \(s_{j}\) — подстрока \(s_{k}\), а \(s_{k}\) — подстрока \(s_{i}\).
Строка \(a\) является подстрокой \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) символов из начала и нескольких (возможно, ни одного или всех) символов из конца.
Необходимо выяснить, сколько сражений будет проведено на экзамене в этом году.
Выходные данные
Необходимо вывести единственное число — количество сражений на экзамене в этом году.
Примечание
В первом примере hidan сражается с dan, а hanabi сражается с nabi, который также сражается с bi. Ниндзя с именами hanabi и bi не сражаются, поскольку есть ниндзя с именем nabi, из-за которого для этой пары не выполняется третье условие.
Во втором примере сражения происходят между abacaba и acaba, abacaba и abaca, acaba и aca, abaca и aca.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
hidan
dan
hanabi
bi
nabi
|
3
|
|
2
|
4
abacaba
abaca
acaba
aca
|
4
|