시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 100 32 29 41.429%

문제

이진수 씨는 이진수를 사랑한다. 그의 하루 일과는 하루 종일 이진수 두 개를 생각해놓고, 그 두 수의 곱을 "오늘의 이진수"로 선정한다. 그리고 예쁜 종이를 한 장 사와 "오늘의 이진수"를 적은 후 액자에 전시한다. 그러나 그런 진수씨에게도 시련이 찾아왔으니, 종이를 사기 위해 나온 도중에 "오늘의 이진수"를 잊어버리고 만 것이다. 하지만, 진수 씨가 오늘 하루 생각해 놓은 두 이진수에 대해서는 어렴풋이 기억하고 있다.

 

그 두 이진수를 A와 B라고 하자. 진수 씨가 기억하는 사실은 다음과 같다. A와 B는 N개의 비트로 이루어져 있다. A의 모든 비트는 1이다. 하지만 B의 일부 비트는 기억하지 못한다. 여기서 "오늘의 이진수"를 어느 정도 추측해 볼 수 있다.

예를 들어, N = 4라면 A = 1111이다. 여기서 B = ?00?라고 해보자. ?는 기억하지 못하는 비트를 의미한다. 그렇다면 B는 0000, 0001, 1000, 1001중 하나일 것이다. 따라서 이 경우 "오늘의 이진수"는 A×B, 즉 0, 1111, 1111000, 10000111중 하나일 것이다. B는 leading zero를 포함할 수 있지만, "오늘의 이진수"는 leading zero를 생략한다. 즉, B는 맨 앞 자리가 1이 아닐 수 있지만, 진수씨가 "오늘의 이진수"를 적을 때에는 A×B=0일 때를 제외하면 맨 앞자리가 반드시 1이 되도록 0을 생략한다.

진수 씨는 "오늘의 이진수"에 비해 너무 크거나 작은 종이를 사고 싶지 않다. 따라서 "오늘의 이진수"를 쓸 때, 가능한 최대 자릿수와 최소 자릿수를 구해보고자 한다. 하지만, 진수 씨는 그의 일생 동안의 경험으로 큰 이진수를 빠르게 곱하는 것은 매우 어렵다는 것을 알고 있다. 따라서 여러분이 그 답을 대신 구해주자.

입력

첫 번째 줄에 테스트케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 

두 번째 줄부터 T개의 줄에 걸쳐, A와 B의 길이 N(1 ≤ N ≤ 1,000,000)과 B가 공백으로 구분되어 주어진다. B는 0, 1, ?로 이루어져 있으며, ?는 해당 비트를 기억하지 못함을 의미한다.

출력

T개의 줄에 걸쳐, 각 테스트케이스에 대해 "오늘의 이진수"의 최대 자릿수와 최소 자릿수를 공백으로 구분하여 출력한다.

예제 입력 1

2
4 0?1?
4 ?00?

예제 출력 1

7 5
8 1

힌트

 

이진수의 곱셈 역시 십진수를 곱하는 것과 유사한 방식으로 계산할 수 있다.