Федот — дизайнер, ему поручена ответственная работа по художественной укладке плитки черного и белого цвета. Его последнее задание — уложить черные и белые плитки в квадрате n × n.
Федот любит свою работу и всегда тщательно готовится к каждому проекту. Федот считает, что два квадрата похожи, если один из них можно получить из другого несколько раз заменив цвета в какой-то строке или столбце на противоположные.
Все эти квадраты являются похожими, и никакой другой не похож на них
Федот заметил, что клиенты никогда не смотрят на всю работу целиком, обычно поле их зрения ограничивается квадратом k × k. Для оценки эскизов он ввел специальную величину — сложность. Она равна числу пар не похожих друг на друга квадратов k × k, которые встречаются в картине.
Методом проб и ошибок Федот установил, что клиентам нравятся картины определенной сложности. Слишком большая сложность похожа на хаос, а слишком малая навевает скуку, считает Федот.
Прежде чем класть плитку, Федот подготовил несколько эскизов. Помогите Федоту вычислить их сложность.
Входные данные
Первая строка входного файла содержит два целых числа n и k (1 ≤ k ≤ n ≤ 500). Следуюшие n строк содержат описание эскиза. Каждая из них имеет длину n и состоит из символов b и w, которые соответствуют белому и черному цветам плиток.
Выходные данные
В первой строке выходного файла выведите одно целое число q — сложность картины.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2 1
bw
wb |
0 |
| 2 |
3 2
bwb
wbb
bbw |
3 |