Morphing — это весело
Morphic — это дерево, которое растет очень быстро, принося радость своему владельцу. Оно состоит из одного ствола, представляющего собой ряд клеток, расположенных одна над другой. Каждая клетка имеет один из n возможных цветов, которые определяют, как она мутирует ночью, когда никто не может её видеть. Флористы обозначают эти цвета первыми n маленькими буквами английского алфавита и точно знают, на сколько клеток и каких цветов делится клетка каждого цвета. Они записали свои знания в виде n непустых слов, каждое из которых представляет собой результирующую последовательность цветов.
Семя Morphic имеет одну клетку цвета a и прочно укоренено в земле. Пока Morphic жив, каждую ночь все его клетки одновременно изменяются в соответствии с вышеупомянутыми правилами, что может привести к экспоненциальному росту, так как каждая новая клетка имеет тот же размер, что и исходная. Например, если правила гласят, что a становится ab, а b становится ca, то через две ночи семя превратится в ствол, состоящий из 4 клеток: abca.
Поэтому верхушка Morphic обычно скрыта в облаках. Единственный способ узнать, жив ли он, — это проверить, меняется ли видимая часть ствола. Для этого можно построить невероятно высокую (но все же постоянной высоты) башню и наблюдать с её вершины фиксированный фрагмент ствола.
Как вы легко можете заметить, достаточно наблюдать за первыми k клетками снизу для некоторого фиксированного k, или, независимо от того, насколько высока башня, вы не сможете с уверенностью сказать, умер ли Morphic. Последнее происходит, когда для каждого k правила приводят к тому, что k-я клетка в конечном итоге перестает менять цвета, даже если дерево все еще живо и мутирует.
Чтобы избежать траты денег на строительство таких огромных башен, вам нужно написать программу, которая определяет, возможно ли следить за состоянием здоровья Morphic.
Входные данные
Входные данные содержат несколько описаний Morphic. Первая строка содержит количество описаний t (t ≤ 10^4), которые следуют далее. Каждое из них начинается с количества цветов n (1 ≤ n ≤ 26). Далее следуют n строк, содержащих правила, по которым растет Morphic. i-я строка описывает последовательность цветов в порядке снизу вверх, полученную из одной клетки i-го цвета. Каждая строка содержит не более 100 строчных английских букв.
Выходные данные
Для каждого теста выведите одну строку, содержащую "YES", если строительство башни бессмысленно (в смысле: YES, мы можем сэкономить деньги!). В противном случае выведите "NO".