석표는 유전자를 가지고 놀고 있다.

유전자는 A, T, C의 세 종류의 문자로 이루어진 문자열이다.

석표는 기계를 한 번 작동시켜서 유전자에서 원하는 두 글자의 위치를 바꿀 수 있다.

석표에게는 두 유전자 S, T를 가지고 있고 둘의 길이는 모두 N이다.

석표는 두 유전자에서 l번째 글자부터 r번째 글자까지를 잘라내어 가지고 논다. (가장 앞글자는 0번째)

석표는 S에서 잘라낸 유전자를 T에서 잘라낸 것과 같게 만들기 위해 최소 몇 번이나 기계를 써야할지 궁금해졌다.

호기심이 많은 석표는 이런 질문을 Q개의 l, r쌍에 대해 가지고 있다.

각각의 질문을 대답하는 프로그램을 만들어보자.

DNA timer 1s memory 512MB

DNA 1s 512MB