Bessie는 자고 싶지만 농장의 불빛 때문에 잠들지 못하고 있다. 어떻게 불을 끌 수 있을까?
Bessie에게는 길이가 $N$인 비트 문자열 두 개가 있다 ($2\le N\le 20$). 각각 전등의 배열과 스위치의 배열을 나타낸다. 각 전등은 켜져 있거나(1) 꺼져 있다(0). 각 스위치는 활성 상태이거나(1) 비활성 상태이다(0).
한 번의 행동은 다음 연산을 이 순서대로 수행하는 것이다.
- 정확히 하나의 스위치를 전환한다. 비활성 상태이면 활성 상태로 만들고, 그 반대도 마찬가지이다.
- 각 활성 스위치에 대해 대응하는 전등의 상태를 전환한다. 켜져 있으면 끄고, 그 반대도 마찬가지이다.
- 스위치를 오른쪽으로 한 칸 순환 이동한다. 구체적으로, 스위치에 대응하는 비트 문자열이 처음에 $s_0s_1\dots s_{N-1}$이라면 $s_{N-1}s_0s_1\dots s_{N-2}$가 된다.
위 문제의 $T$개 사례 ($1\le T\le 2\cdot 10^5$)에 대해, 모든 전등을 끄는 데 필요한 최소 행동 횟수를 구하여라.
입력
첫 번째 줄에는 $T$와 $N$이 주어진다.
다음 $T$개의 줄에는 각각 길이가 $N$인 비트 문자열 한 쌍이 주어진다.
출력
각 쌍에 대해 모든 전등을 끄는 데 필요한 최소 행동 횟수를 출력하여라.
예제
입력 1
4 3 000 101 101 100 110 000 111 000
출력 1
0 1 3 2
참고
- 첫 번째 테스트 케이스: 모든 전등이 이미 꺼져 있다.
- 두 번째 테스트 케이스: 첫 번째 행동에서 세 번째 스위치를 전환한다.
- 세 번째 테스트 케이스: 첫 번째 행동에서 첫 번째 스위치를, 두 번째 행동에서 두 번째 스위치를, 세 번째 행동에서 다시 두 번째 스위치를 전환한다.
- 네 번째 테스트 케이스: 첫 번째 행동에서 첫 번째 스위치를, 두 번째 행동에서 세 번째 스위치를 전환한다.
각 경우에서 이 횟수가 필요한 최소 행동 횟수임을 보일 수 있다.
입력 2
1 10 1100010000 1000011000
출력 2
2
참고
모든 전등을 끄려면 $2$번의 행동이 필요함을 보일 수 있다.
- 첫 번째 행동에서 일곱 번째 스위치를 전환하고, 두 번째 행동에서 같은 스위치를 다시 전환한다.
서브태스크
- 입력 3-5: $N \le 8$
- 입력 6-13: $N\le 18$
- 입력 14-20: 추가 제한이 없다.
문제 작성: William Yue, Eric Yang, Benjamin Qi