페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5473

Lights Off 4초 1024MB

문제

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≤N≤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:

 

1. Toggle exactly one switch (set it to active if it is inactive, or vice versa).

2. For each active switch, toggle the state of the corresponding light (turn it off if it is on, or vice versa).

3. Cyclically rotate the switches to the right by one. Specifically, if the bit string corresponding to the switches is initially s0s1 … s N-1 then it becomes sN-1s0s1…sN-2.

 

For T (1≤T≤2⋅105) 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. 


예제1

입력
4 3

000 101
101 100
110 000
111 000
출력
0

1
3
2

예제2

입력
1 10

1100010000 1000011000
출력
2


출처

USACO 2023 January Gold

역링크 공식 문제집만