Scientist Aftab has made a groundbreaking discovery regarding chromosomal crossover today!

Before going into details let’s understand a few definitions first. According to Holland’s convention, a gene is represented by either 0 or 1. A chromosome is a string of genes. While in crossover, two parental chromosomes arbitrarily get separated at the exact same position forming four non-empty parts.  And these parts join together to form two offspring. For example, let A and B be two parental chromosomes of length N. After cutting those at arbitrary position X, we get four parts LA, RA, LB, RB. Here LA is made of A[0,…,X], RA is made of A[X+1,…,N-1] and the same for LB and RB. After applying crossover, we get two offspring O1=LA+RB andO2= LB+RA. Here ‘+’ is string concatenation operator.

Scientist Aftab’s claim is that, the fittest offspring among O1 and O2 is the one which is greater in value. Here the value of a chromosome is computed keeping in mind that this is a bitstring with the leftmost bit being the Most Significant Bit (MSB) and the rightmost bit is the Least Significant Bit (LSB).

Although scientist Aftab is a great genetics researcher, he is not good at handling chromosomes of large size. So he is seeking your help. You will be given two chromosomes of length N. And you will have to output the decimal value modulo 10⁹+7 of the fittest offspring after applying crossover.

Input

Input starts with an integer T(<=30), denoting the number of test cases. Each case contains two lines containing two strings of same length N (2<=N<=100000). Strings will contain only 0’s and 1’s.

Output

For each case of input, print the case number followed by the decimal value modulo 10⁹+7 of the fittest string after the crossover.

Sample I/O

Explanation of Sample I/O

For the first case, the fittest offspring is 110101, whose decimal value modulo 10⁹+7 is 53.