Guessing Game I

Interview

Time limit1sMemory limit128 MB

Summary

Compare a 4-digit secret and a guess digit by digit, count exact-position matches as circles and remaining cross-position matches as squares, with duplicates matched once.

Level: Easy3 of 10
Topics: Implementation, Hash map, String, Simulation
Solved: No attempts yet

Problem

After a long trek through treacherous mountains, Bilbo and the dwarves arrive at the West Gate of the mines of Puzzlia, built by a mathematically inclined Dwarf King. The gate will not open unless they correctly guess a 4-digit number, which we call the secret.

Above the gate are 8 shapes: 4 circles and 4 squares. Each time a guess is spoken aloud, some of these shapes light up according to the rules below. Let guess be the number that is spoken, and compare guess with the secret digit by digit:

If a digit of guess equals the digit of the secret at the same position, one circle lights up.
If a digit of guess equals a digit of the secret at a different position, one square lights up.

Both the secret and the guess may contain repeated digits. Duplicates are handled as follows: each digit of the secret can be matched to at most one digit of the guess (and vice versa), and exact-position matches take priority. So first count all exact-position matches (circles), then look for out-of-position matches (squares) among the digits that are still unmatched.

Examples of the rule:

secret = 1234, guess = 1357: the "1" is an exact match (one circle) and the "3" is an out-of-position match (one square). The other two digits match nothing.
secret = 1234, guess = 1122: the first "1" is an exact match (one circle); the second "1" matches nothing (the secret's only "1" is already used); the first "2" is an out-of-position match (one square). Result: 1 circle, 1 square.
secret = 1311, guess = 1122: one circle for the exact match at position 1, and one square for an out-of-position "1". Result: 1 circle, 1 square.
secret = 0011, guess = 0213: two exact matches and no out-of-position matches. Result: 2 circles, 0 squares.

Given the secret and the guess, report how many circles and how many squares light up.

Input

The first line contains the number of test cases $T$ ( $T < 100$ ).

Each of the next $T$ lines contains two integers: the secret followed by the guess. Both integers satisfy $0 \le \text{value} \le 9999$ .

Because a number may have fewer than four digits, pad it with leading zeros to four digits before comparing (for example, the integer $1$ is treated as $0001$ ).

Output

For each test case, print one line in exactly this format:

For secret = S and guess = G, C circles and D squares will light up.

Here S and G are the secret and the guess printed as the integer values read from the input, C is the number of circles (exact-position matches), and D is the number of squares (out-of-position matches).

Examples1

Example 1

Input

Expected output

For secret = 1234 and guess = 1111, 1 circles and 0 squares will light up.
For secret = 5678 and guess = 5678, 4 circles and 0 squares will light up.
For secret = 4444 and guess = 4444, 4 circles and 0 squares will light up.
For secret = 1234 and guess = 1211, 2 circles and 0 squares will light up.
For secret = 1122 and guess = 2211, 0 circles and 4 squares will light up.