Во многих прикладных задачах, таких как поиск в сети или расшифровка генома, требуется совершать некоторые действия со строками. Например, часто требуется по некоторым данным о строке восстановить ее саму. Вам даны две строки \textbf{S_1} и \textbf{S_2}. Известно, что одна из них была суффиксом искомой строки \textbf{S}, а другая --- ее префиксом. Также известна длина искомой строки \textbf{L}, а также то, что строка \textbf{S} состояла только из строчных букв латинского алфавита. Необходимо определить число строк, удовлетворяющих этим ограничениям. Так как это число может быть достаточно большим, то необходимо вывести его по модулю \textbf{m}. \InputFile Первая строка содержит одно целое число \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{100}) --- количество наборов входных данных, которые необходимо обработать. Описание каждого из наборов входных данных содержит три строки. Первая из них содержит два целых числа: \textbf{L} и \textbf{m} (\textbf{1} ≤ \textbf{L} ≤ \textbf{10^9}, \textbf{1} ≤ \textbf{m} ≤ \textbf{10^4}). Вторая и третья строки содержат соответственно строки \textbf{S_1} и \textbf{S_2}. Они непусты, состоят из строчных букв латинского алфавита, их длины не превышают \textbf{200} символов. \OutputFile Для каждого набора входных данных выведите в отдельной строке остаток от деления числа строк, удовлетворяющих требованиям условия, на \textbf{m}.