A. Image

time limit per test

2 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

You have an image file of size 2×22×2, consisting of 44 pixels. Each pixel can have one of 2626 different colors, denoted by lowercase Latin letters.

You want to recolor some of the pixels of the image so that all 44 pixels have the same color. In one move, you can choose no more than two pixels of the same color and paint them into some other color (if you choose two pixels, both should be painted into the same color).

What is the minimum number of moves you have to make in order to fulfill your goal?

Input

The first line contains one integer tt (1≤t≤10001≤t≤1000) — the number of test cases.

Each test case consists of two lines. Each of these lines contains two lowercase letters of Latin alphabet without any separators, denoting a row of pixels in the image.

Output

For each test case, print one integer — the minimum number of moves you have to make so that all 44 pixels of the image have the same color.

Example

input

Copy

5

rb

br

cc

wb

aa

aa

ab

cd

yy

xx

output

Copy

1
2
0
3
1

Note

Let's analyze the test cases of the example.

In the first test case, you can paint the bottom left pixel and the top right pixel (which share the same color) into the color r, so all pixels have this color.

In the second test case, two moves are enough:

• paint both top pixels, which have the same color c, into the color b;
• paint the bottom left pixel into the color b.

In the third test case, all pixels already have the same color.

In the fourth test case, you may leave any of the pixels unchanged, and paint all three other pixels into the color of that pixel in three moves.

In the fifth test case, you can paint both top pixels into the color x.

解题说明：此题是一道模拟题，为了保证最后4块颜色一致，而且每次换色最多只能换2块。可以换个角度思考，先统计出里面总共有多少种颜色，然后再更换到只保留一种，更换次数就是颜色总数减去1.

#include
#include
 
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int i, j;
		char p[2][2];
		for (i = 0; i<2; i++)
		{
			for (j = 0; j<2; j++)
			{
				scanf(" %c", &p[i][j]);
			}
		}
		int k[27] = { 0 };
		for (i = 0; i<2; i++)
		{
			for (j = 0; j<2; j++)
			{
				k[p[i][j] - 96]++;
			}
		}
		int length = 0;
		for (int i = 0; i<27; i++)
		{
			if (k[i]>0)
			{
				length++;
			}
		}
		printf("%d\n", length - 1);
	}
	return 0;
}