Lights Off

시간 제한4초메모리 제한1024 MB

요약

길이 N인 전구 문자열과 스위치 문자열이 주어지고, 한 번의 이동은 스위치 하나를 뒤집고 활성 스위치에 대응하는 전구를 토글한 뒤 스위치를 오른쪽으로 한 칸 회전시킬 때, 모든 전구를 끄는 최소 이동 횟수를 구한다.

난이도: 보통10점 중 6점
유형: 완전 탐색, 비트 연산, 수학, 문자열
정답자: 아직 제출이 없습니다

문제

Bessie wants to go to sleep, but the farm's lights are keeping her awake. How can she turn them off?

Bessie has two bit strings of length $N$ ( $2\le N\le 20$ ), representing a sequence of lights and a sequence of switches, respectively. Each light is either on (1) or off (0). Each switch is either active (1) or inactive (0).

A *move* consists of the following sequence of operations:

Toggle exactly one switch (set it to active if it is inactive, or vice versa).
For each active switch, toggle the state of the corresponding light (turn it off if it is on, or vice versa).
Cyclically rotate the switches to the right by one. Specifically, if the bit string corresponding to the switches is initially $s\_0s\_1\dots s\_{N-1}$ then it becomes $s\_{N-1}s\_0s\_1\dots s\_{N-2}$ .

For $T$ ( $1\le T\le 2\cdot 10^5$ ) instances of the problem above, count the minimum number of moves required to turn all the lights off.

입력

First line contains $T$ and $N$ .

Next $T$ lines each contain a pair of length- $N$ bit strings.

출력

For each pair, the minimum number of moves required to turn all the lights off.

예제2

예제 1

입력

예상 출력

예제 2
입력
```
1 10
1100010000 1000011000
```
예상 출력
```
2
```