Европейская математическая олимпиада среди девочек (EGMO). 2023 год. Словения

Пусть $k$ — целое положительное число. У Лекси есть словарь $\mathcal{D}$, состоящий из нескольких $k$-буквенных слов, содержащих только буквы $A$ и $B$. В каждую клетку таблицы $k \times k$ Лекси хочет вписать либо букву $A$, либо букву $B$ так, чтобы каждый столбец таблицы содержал слово из $\mathcal{D}$ при чтении сверху вниз, и каждая строка таблицы содержала слово из $\mathcal{D}$ при чтении слева направо.
   Чему равно наименьшее целое число $m$ такое, что если $\mathcal{D}$ содержит не менее $m$ различных слов, то Лекси заведомо сможет заполнить таблицу нужным образом, независимо от того, какие слова находятся в $\mathcal{D}$?