엘페티라 뒤집기

Fouad는 페티라가 먹고 싶어서 페티라 식당에 가서 하나를 주문했다. 요리사는 한 변의 길이가 N인 정사각형 페티라를 N × N 행렬 형태로 판다고 말했다.

페티라 표면에는 1 × 1 칸마다 세메세마가 하나씩 있다. 각 세메세마는 페티라의 윗면 또는 아랫면에 있을 수 있지만, 한 칸의 양쪽 면에 세메세마가 두 개 있을 수는 없다.

Fouad는 요리사가 페티라를 뒤집는 것을 보는 걸 좋아하는데, 이번 페티라는 평소보다 훨씬 흥미로웠다. 요리사는 무작위로 (균일하게) 직사각형 부분행렬을 하나 고르고 그 자리에서 뒤집는다. 페티라의 부분행렬을 뒤집을 때마다 윗면에 있던 세메세마는 아랫면으로 가고, 그 반대도 마찬가지다.

페티라의 초기 상태가 주어지고 요리사가 뒤집기를 K번 했다는 것을 알 때, Fouad는 윗면에 세메세마가 몇 개 있을지 궁금해졌다. 그래서 그는 윗면에 있는 세메세마 개수의 기댓값을 구해 달라고 부탁한다.

입력의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 T가 주어진다.

각 테스트 케이스의 첫 줄에는 공백으로 구분된 두 정수 N과 K (1 ≤ N ≤ 300, 0 ≤ K ≤ 300)가 주어진다. N은 페티라 행렬의 크기이고, K는 뒤집기 연산의 횟수다.

그다음 N개의 줄이 주어지며, i번째 줄에는 N개의 공백으로 구분된 값 Fi1, ..., FiN (Fij ∈ {0, 1})이 있다. Fij는 페티라의 i번째 행 j번째 칸의 윗면 상태를 나타낸다 (1은 초기 상태에서 세메세마가 윗면에 있음을, 0은 아랫면에 있음을 뜻한다).

각 테스트 케이스마다 뒤집기 연산을 정확히 K번 한 뒤 페티라에 있는 세메세마 개수의 기댓값을 소수점 다섯째 자리까지 반올림해 한 줄에 출력한다.