I have been asked to set a problem by spoj, what do I do now ? Lets see the standard stuff in most of the programming contests and make one problem out of it. Hmm... many problems are having Binary digits, Grids, Paths, Coins, Maximize or Minimize something, so let me mix them all now in to one problem, the one problem to rule them all ;)

Lets have a grid of size N x M having N rows and M columns, and put gold coins in it. How many in each cell ? , lets involve binary here. I'll give you two binary strings A[1...N] and B[1...M]. Cell (i, j) (1-based indexing) Row-i and Column-j in the grid contains A[i] * B[j] gold coins. From a cell (i, j), you can move to any of the 4 adjacent cells (i-1, j), (i+1, j), (i, j-1), (i, j+1) in one step. I want a path of minimum length from top-left cell (1, 1) to bottom-right cell (N, M), and the value of this path = number of gold coins it covers. Find the maximum value of such a path. Not every one wants to become a Raja, also find the minimum value of such a path.

Input

First line contains T [number of test cases, around 10 ]. T cases follow, each having 2 lines, "N A" and "M B" (quotes for clarity only). [1 <= N, M <= 100, 000 and each character in A, B is either 0 or 1].

Output

For each test case, print the maximum value of a path followed by the minimum value of a path, in the same line, separated by a single space. Output of each case should be in a separate line.

Example

Input:
2
4 1001
3 110
5 01111
3 110

Output:
3 1
5 0

Explanation

Case 1: A Maximum path in bold

110
000
000
110

Case 1: A Minimum path in bold

110
000
000
110