For this problem we are much indebted to Clive Fraser aka CSFPython!
In information theory, the Hamming distance between two strings of equal length is the number of positions at
which the corresponding symbols are different. In other words, it measures the minimum number of substitutions
required to change one string into the other, or the minimum number of errors that could have transformed one
string into the other. It is named after the American mathematician
Richard Hamming.
In this problem we will be
dealing with code words which are binary strings. For example, the two code words 0110 and 1100 are different in
the first and third positions (the bits in positions 2 and 4 are the same in each string). So the Hamming
distance between these two words is 2. The words 1010 and 0101 are different at each of the 4 bit
positions, so the Hamming distance is 4. 1100 and 1100 are the same in all 4 bit positions so the
Hamming distance is 0.
In communication systems where errors in transmission are common, it is a good idea to use a set of code words
with a Hamming distance of 3 or even 4 between each pair of code words. This means that more than one error
has to occur within a particular code word before it is likely to be mistaken for a different valid code word.
A word which has the same Hamming distance from each of two valid code words could potentially be mistaken for
either of them. In this problem we will be concerned with words which have an equal Hamming difference from
each of two given words (of the same length).
For example, if we consider the two code words 011 and 110 we can find 4 words of the same length (3)
which have an equal Hamming distance from each of these two words. The words 010 and 111 have a Hamming
distance of 1 from each of the given code words. The words 000 and 101 have a Hamming distance of 2 from
each of the given code words. These are the only 4 binary strings of length 3 which have equal Hamming
distance from each of the words 011 and 110. In each of the problems which follow, you will be given a pair
of code words (of equal length) and are asked to find the number of binary strings of the same length which have
equal Hamming difference from each of the given words. None of the code words will have a length greater than 70.
The first line of the problem will be a single integer N denoting the number of test cases. Each test case
will consist of a single line containing 2 binary code words of the same length, separated by a space. For
each test case you must find the number of binary strings of the same length which have equal Hamming difference
from each of the given words. Give these answers, separated by spaces, as a single string.
Example:
input:
3
011 110
110011 011000
010011100 100100101
answer:
4 24 160