У лисы Сиель есть доска, расчерченная на n рядов и n колонок. Таким образом, доска состоит из n × n ячеек. Каждая ячейка содержит либо символ '.', либо символ '#'.
Крест на доске — это связное множество из ровно пяти клеток доски, которое выглядит как крест. Рисунок ниже показывает, как выглядит крест.
Сиель хочет нарисовать несколько (возможно, ноль) крестов на доске. Каждый крест должен состоять ровно из пяти клеток с символами '#', и каждая клетка с символом '#' должна принадлежать некоторому кресту. Ни одна клетка не может принадлежать двум крестам.
Пожалуйста, подскажите Сиель, может ли она нарисовать на доске кресты описанным способом.
Выходные данные
Выведите единственную строку, содержащую слово "YES", если Сиель может нарисовать кресты так, как описано выше. В противном случае, выведите единственную строку, содержащую слово "NO".
Примечание
В первом примере можно нарисовать два креста. Рисунок ниже показывает, как они выглядят.
Во втором примере доска содержит 16 клеток с '#', но каждому кресту требуется 5 клеток. Так как 16 не кратно 5, лиса не сможет покрыть крестами все помеченные символом '#' клетки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
.#...
####.
.####
...#.
.....
|
YES
|
|
2
|
4
####
####
####
####
|
NO
|
|
3
|
6
.#....
####..
.####.
.#.##.
######
.#..#.
|
YES
|
|
4
|
6
.#..#.
######
.####.
.####.
######
.#..#.
|
NO
|
|
5
|
3
...
...
...
|
YES
|