Коварный брендинг
Бренд-дизайнер разработал стратегию, которую вы считаете ключом к успеху вашей компании, а значит, и вас. Эта стратегия заключается в использовании названия бренда, которое может быть разложено на две пары часто используемых повседневных слов, и затем воздействии на потребителя четырьмя словами в коротких эпизодах сенсорной бомбардировки. Слабый ум потребителя будет потрясен, и бренд затем легко проникнет в долгосрочную память жертвы. Ваша задача — написать программу, которая просеивает словарь в поисках комбинаций из четырех слов (не обязательно различных), скажем A, B, C и D, которые удовлетворяют уравнению A+B=C+D, где '+' обозначает конкатенацию, '=' обозначает точное совпадение строк, длина слова A строго меньше длины слова C, и все четыре строки не пусты.
Входные данные
Входные данные состоят из нескольких случаев, где для каждого случая используется один словарь. Случай начинается с целого числа W (1 ≤ W < 100000), которое указывает количество слов в словаре на отдельной строке. Каждая из следующих W строк содержит одно слово. Слова расположены в произвольном порядке и все различны в пределах тестового случая. Каждое слово — это строка, состоящая из L строчных букв и не содержащая пробелов. 1 ≤ L ≤ 30. Ввод завершается нулем на отдельной строке.
Выходные данные
Выходные данные состоят из одного целого числа, на отдельной строке, которое представляет количество уравнений, которые могут быть сформированы.