Jinsu's Daily Routine

Jinsu loves binary numbers. His daily routine is to think of two binary numbers all day and pick their product as "today's binary number." He then buys a sheet of pretty paper, writes "today's binary number" on it, and puts it in a frame. But trials come even to Jinsu: while out buying the paper, he forgets "today's binary number." However, he vaguely remembers the two binary numbers he thought of today.

Call those two binary numbers A and B. What Jinsu remembers is the following. A and B consist of N bits. Every bit of A is 1. But he does not remember some bits of B. From this, we can guess "today's binary number" to some extent.

For example, if N = 4 then A = 1111. Suppose B = ?00?. The ? means an unremembered bit. Then B is one of 0000, 0001, 1000, 1001. So in this case "today's binary number" is one of A×B, namely 0, 1111, 1111000, 10000111. B may include leading zeros, but "today's binary number" omits leading zeros. That is, B may not start with 1, but when Jinsu writes "today's binary number" he omits zeros so that the first digit is always 1, except when A×B=0.

Jinsu does not want to buy paper that is too large or too small for "today's binary number." So when writing "today's binary number," he wants to find the maximum and minimum possible number of digits. But from his life experience, Jinsu knows that multiplying large binary numbers quickly is very hard. So let us find the answer for him instead.

The first line gives the number of test cases T(1 ≤ T ≤ 20).

From the second line, across T lines, the length N(1 ≤ N ≤ 1,000,000) of A and B and the string B are given, separated by a space. B consists of 0, 1, and ?, where ? means the corresponding bit is unremembered.

Across T lines, for each test case, print the maximum and minimum number of digits of "today's binary number," separated by a space.

Binary multiplication can also be computed in a way similar to decimal multiplication.