Марко често игра разни игри на својот мобилен телефон, а една од неговите омилени е играта Забранети тројки. Во оваа игра, дадени се две текстуални низи составени само од знаците A и B. Притоа, двете текстуални низи имаат еднаков број на знаци, и за двете низи важи правилото дека не е дозволено да се појави еден ист знак (A или B) три пати по ред (или повеќе од трипати). На пример, двете текстуални низи може да бидат ABBAAB и BBABAB (истите имаат еднаков број на знаци - по 6, и не се појавува ниту A ниту B три или повеќе пати последователно).

Нека ја означиме првата текстуална низа со X, а втората текстуална низа со Y. Целта на играта е да се дојде од низата X до низата Y, со минимален број на операции на заменување на знак (А во B или B во А). Со други зборови, прашањето е колку најмалку операции се потребни доколку:

    - Започнуваме од низата X
    - Со една операција, можеме да замениме еден знак (А во B или B во А)
    - Притоа, не е дозволено, во ниту еден момент, менување на знак во целната низа Y, или пак да се појави некој знак (A или B) три или повеќе пати последователно

Напишете програма која ќе го определи минималниот број на потребни операции.

Влез

Во првиот ред е запишан еден цел број N (1 <= N <= 6000), кој го означува бројот на знаци во двете текстуални низи. Во вториот ред е запишана текстуалната низа X, а во третиот ред текстуалната низа Y. Двете низи ќе имаат по точно N знаци (‘A’ и ‘B’), и ниту еден знак нема да се појави три или повеќе пати последователно.

Забелешка: Во тест случаи кои носат најмалку 18% од поените, бројот на знаци N ќе биде помал или еднаков на 15 (N <= 15).
Во други тест случаи кои носат најмалку 6% од поените, знаците и во двете текстуални низи ќе алтернираат (т.е. нема да има два еднакви знака едноподруго, односно и низата X и Y ќе бидат од типот ABABA… или BABAB…).

Излез

Отпечатете го бараниот минимален број на операции.

Ограничувања

Временско ограничување: 100 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
3
BAB
AAB

излез
1

влез
4
ABBA
BAAB

излез
4

влез
5
BBAAB
BABAB

излез
4

Објаснување за првиот пример: BAB -> AAB (замена на првиот знак од B во A).
Објаснување за вториот пример: ABBA -> AABA -> BABA -> BABB -> BAAB.
Објаснување за третиот пример: BBAAB -> ABAAB -> ABBAB -> AABAB -> BABAB.