Mathematicians have always loved generalizing mathematics to everything. They even contributed lots of optimizations and valuable formulas to Computer Science. Have you heard about String Multiplication? What do you think will happen if we write the following code in python?

print (3 * “abc”);

As you might have guessed, it prints “abcabcabc”. It is equal to print(“abc” + “abc” + “abc”);

We define string S is divisible by string T, if there is some non-negative integer k, which satisfies the equation S=k*T .

Your task is simple. Given two strings S and T. What is the minimum number of characters which should be removed from S, so S is divisible by T?

Input

The first line of the input contains Q the number of the test cases. (1≤Q≤100)

Each test case consists of two lines. 

The first line contains string S consisting of lowercase English letters. (0≤|S|≤10⁴)

The second line contains string T consisting of lowercase English letters. (0<|T|≤10⁴)

Output

For each test case print a single integer, the minimum number of characters which should be removed.

Example

Input:
4
babbaba
ab
dictate
acid
abc
p
q
Output:
3
7
0
1