Hamming Distance

Interview

Time limit1sMemory limit128 MB

Summary

For each test case, count the positions where two equal-length binary strings differ and print the Hamming distance.

Level: Easy2 of 10
Topics: String, Implementation
Solved: No attempts yet

Problem

The Hamming distance is the number of positions at which two binary numbers of equal length differ. Given two binary numbers, write a program that computes their Hamming distance.

Input

The input consists of several test cases. The first line contains the number of test cases $T$ . Each test case consists of two lines, each containing one binary number. Within a test case, the two binary numbers have the same length, which does not exceed 100 digits.

Output

For each test case, compute the Hamming distance and print it on its own line in the form Hamming distance is X., where $X$ is the Hamming distance.

Examples3

Example 1

Input

4
0
1
000
000
1111111100000000
0000000011111111
101
000

Expected output

Hamming distance is 1.
Hamming distance is 0.
Hamming distance is 16.
Hamming distance is 2.

Example 2
Input
```
1
1010
1010
```
Expected output
```
Hamming distance is 0.
```
Example 3
Input
```
1
1111
0000
```
Expected output
```
Hamming distance is 4.
```