A. Разворачивай и конкатенируй
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Real stupidity beats artificial intelligence every time.
— Terry Pratchett, Hogfather, Discworld

Вам дана строка $$$s$$$ длины $$$n$$$ и число $$$k$$$. Обозначим за $$$rev(s)$$$ развёрнутую строку $$$s$$$ (т.е. $$$rev(s) = s_n s_{n-1} ... s_1$$$). Вы можете выполнять два типа операций:

  • заменить строку $$$s$$$ на $$$s + rev(s)$$$
  • заменить строку $$$s$$$ на $$$rev(s) + s$$$

После выполнения ровно $$$k$$$ операций (возможно, различных) над строкой, какое количество различных строк вы можете получить из начальной строки $$$s$$$?

Мы обозначили конкатенацию строк $$$s$$$ и $$$t$$$ как $$$s + t$$$. Другими словами, $$$s + t = s_1 s_2 ... s_n t_1 t_2 ... t_m$$$, где $$$n$$$ и $$$m$$$ - длины строк $$$s$$$ и $$$t$$$ соответственно.

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

Первая строка содержит число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

В следующих $$$2 \cdot t$$$ строках вводится $$$t$$$ наборов входных данных:

Первая строка каждого набора содержит два числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 100$$$, $$$0 \le k \le 1000$$$).

Вторая строка каждого набора содержит одну строку $$$s$$$ длины $$$n$$$, состоящую из строчных латинских букв.

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

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

Можно показать, что при данных ограничениях ответ не превосходит $$$10^9$$$.

Пример
Входные данные
4
3 2
aab
3 3
aab
7 1
abacaba
2 0
ab
Выходные данные
2
2
1
1
Примечание

Рассмотрим первый набор входных данных:

После первой операции строка $$$s$$$ может стать либо aabbaa, либо baaaab. После второй операции $$$s$$$ может принимать только такие 2 значения: aabbaaaabbaa и baaaabbaaaab.