Биби и его папа

Биби вырос, наступила пора покинуть родительское гнездо и отправиться навстречу новым знаниям. Пин не хочет потерять с сыном связь, поэтому решил смастерить для него телеграф.

Чтобы научиться пользоваться телеграфом, Биби должен последовательно отправить с его помощью $$$n$$$ сообщений $$$s_1, s_2, \dots, s_n$$$.

Пин предусмотрел, что с большой вероятностью Биби захочет отправлять одинаковые сообщения, например «hello father», несколько раз, поэтому добавил кнопку «$$$\uparrow$$$», которая загружает в телеграф предыдущее отправленное сообщение.

Таким образом, Биби может отправить сообщение $$$s$$$ одним из двух способов:

набрать сообщение посимвольно и нажать «Enter», выполнив суммарно $$$|s|+1$$$ ($$$|s|$$$ — это длина строки $$$s$$$) нажатие;
если Биби уже отправлял такое же сообщение ранее, нажать на «$$$\uparrow$$$» произвольное количество раз $$$k$$$, загрузив в телеграф $$$k$$$-е по счёту с конца отправленное сообщение, и нажать «Enter», выполнив суммарно $$$k+1$$$ нажатие.

Помогите Биби последовательно отправить все сообщения, выполнив как можно меньшее суммарное число нажатий.

$\text{[math]}$

Входные данные

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора дано целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество сообщений.

В следующих $$$n$$$ строках каждого набора дана последовательность сообщений $$$s_1, s_2, \ldots, s_n$$$, состоящих из строчных и заглавных букв латинского алфавита, а также пробелов. Сообщения разделены переводами строк.

Гарантируется, что сумма длин сообщений по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Также гарантируется, что первый и последний символы каждого сообщения не являются пробелами.

Выходные данные

Для каждого набора входных данных выведите единственное целое число — минимальное количество нажатий, необходимое для отправки всех сообщений.

Пример

Входные данные

4
6
hi
hi
hello father
i am fine
hello father
hi
3
aba
b
aba
6
krosh
pin
ezik
krosh and ezik
pin
goodbye
4
hello krosh
goodbye
hello ezik
goodbye

Выходные данные

Примечание

Во втором наборе входных данных оптимальна следующая последовательность действий: «a», «b», «a», «Enter», «b», «Enter», «$$$\uparrow$$$», «$$$\uparrow$$$», «Enter».

В третьем наборе входных данных одна из оптимальных последовательностей: «k», «r», «o», «s», «h», «Enter», «p», «i», «n», «Enter», «e», «z», «i», «k», «Enter», «k», «r», «o», «s», «h», « », «a», «n», «d», « », «e», «z», «i», «k», «Enter», «$$$\uparrow$$$», «$$$\uparrow$$$», «$$$\uparrow$$$», «Enter», «g», «o», «o», «d», «b», «y», «e», «Enter».

Обратите внимание, что сообщения могут содержать пробелы. Для считывания набора входных данных на языке C++ вы можете использовать представленный ниже сниппет.


#include <iostream>
#include <string>
using namespace std;

void solve() {
    int n; cin » n;
    string tmp; getline(cin, tmp);
    for (int i = 0; i < n; ++i) {
        string s; getline(cin, s);
        // ...
    }
}