Сегодня Миша в очередной раз пришел на урок математики, не сделав домашнее задание. Чтобы наказать ученика, учитель Андрей Владимирович решил дать ему очень сложное, но очень бессмысленное задание.

Андрей Владимирович написал на доске две строки s и t, состоящие из строчных латинских букв. Он напомнил ученикам, что префиксом строки называется строка, полученная удалением нескольких (возможно, нуля) последних символов из исходной строки, а конкатенацией двух строк называется строка, полученная приписыванием второй строки в конец к первой.

После этого учитель попросил выписать на доску все строки, являющиеся конкатенацией некоторого непустого префикса строки s и некоторого непустого префикса строки t. Когда Миша сделал это, Андрей Владимирович спросил, сколько различных строк есть среди выписанных им. Миша потратил практически весь урок, выполняя это задание, но справился с ним. Чтобы больше не тратить время на это, он попросил вас написать программу, которая выполнит это задание сама.