개미

컴퓨터를 좋아하는 사람들이 나무를 좋아하듯, 개미도 나무를 좋아한다. 두 마리의 개미, 왼쪽 개미와 오른쪽 개미가 한 나무의 바깥 윤곽을 따라 걷고 있으며, 그 경로는 위 그림의 점선과 같다. 두 개미는 모두 줄기의 아래쪽 끝에서, 줄기를 사이에 두고 서로 반대편에서 출발한다.

왼쪽 개미는 뿌리에서 멀어지는 방향(위쪽)으로 한 변을 걷는 데 2초, 뿌리로 향하는 방향(아래쪽)으로 걷는 데 1초가 걸린다. 오른쪽 개미는 두 배 빠르므로 위쪽으로는 1초, 아래쪽으로는 0.5초가 걸린다.

두 개미가 만나면 둘 다 즉시 방향을 바꾸어 서로 반대 방향으로 걷기 시작한다. 만약 어떤 개미가 나무에서 땅으로 내려서게 되면, 그 즉시 줄기의 반대쪽 면을 타고 올라가기 시작한다. 개미는 매우 작아서 현미경으로도 보이지 않을 정도이다(그림에서는 설명을 위해 크게 그렸다).

개미들이 두 번째로 방향을 바꾸는 정확한 순간을 구하는 프로그램을 작성하라.

첫째 줄에 정수 $t$ ($1 \le t \le 1000$), 즉 테스트 케이스의 수가 주어진다.

각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 짝수 $n$ ($2 \le n \le 100\,000\,000$), 즉 나무의 변의 개수가 주어진다. 둘째 줄에는 $n/2$개의 문자(숫자와 소문자 a–f)로 이루어진 문자열이 주어지며, 이는 $2n$비트 이진수를 16진수로 나타낸 것이다. 이 수는 오른쪽 개미가 가만히 있다고 가정했을 때, 왼쪽 개미가 나무 전체를 도는 경로를 나타낸다. 비트를 왼쪽부터 읽을 때, 비트가 1이면 왼쪽 개미가 해당 변을 따라 뿌리에서 멀어지는 방향으로, 0이면 뿌리로 향하는 방향으로 걷는다는 뜻이다. 뿌리에는 줄기가 있다. 즉, 뿌리에서 나가는 변은 정확히 하나이다.

입력의 크기는 50 MB를 넘지 않으며, 이는 프로그램이 사용할 수 있는 메모리보다 훨씬 크다.

각 테스트 케이스마다 한 줄씩, 총 $t$줄을 출력한다. 각 줄에는 개미들이 두 번째로 방향을 바꾸는 순간(초)을 기약분수 p/q 형태로 출력한다. 이때 / 양옆에 공백이 없어야 하며, $p$와 $q$는 양의 정수이다. 답이 정수이면 당연히 $q = 1$이다.

각 16진수 숫자는 최상위 비트부터 4개의 비트로 펼쳐진다(예: f는 1111, b는 1011). 이들을 왼쪽부터 이어 붙이면 전체 $2n$비트 수열이 된다.

이 경로는 나무 전체를 한 바퀴 도는 순회이므로, 모든 변은 정확히 두 번(뿌리에서 멀어질 때 한 번, 뿌리로 향할 때 한 번) 지나간다. 따라서 수열에는 항상 1이 $n$개, 0이 $n$개 들어 있다. 두 개미는 같은 닫힌 윤곽을 서로 반대 방향으로 돈다.