Через входной поток поступает несколько строк.

Через входной поток поступает несколько строк.
В первой строке вводится натуральное число N - количество оставшихся строк (тестов).
В каждой из следующих N строк размещено два слова, разделенные пробелом. (Длина каждого слова не превышает 32).
Необходимо для каждой пары слов получить новое слово, так, чтобы окончание первого совпадало с началом второго, например, гора + радуга = горадуга. Это слово надо вывести в стандартный поток вывода.
Если слова возможно соединить несколькими способами, надо выбрать тот, который обеспечивает максимальную общую часть, например папа + папаха = папаха (а не папапаха).

Пример входного потока:
3
шлакоблок окунь
папа папаха
папа мама

Выходной поток:
шлакоблокунь
папаха
папамама