• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

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 number $k \in \mathbb{N} \cup {0}$ which satisfies the equation $S = k \times 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$?

ورودی

The first line of the input contains $Q$ the number of the test cases. $$1 \leq Q \leq 100$$

Each test case consists of two lines. The first line contains string $S$ consisting of lowercase English letters. $$0 \leq |S| \leq 10^4$$

The second line contains string $T$ consisting of lowercase English letters. $$0 \leq |T| \leq 10^4$$

خروجی

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

مثال‌ها

ورودی نمونه ۱

5
babbaba
ab
dictate
acid

abc
p
q
dddabcbcbcacccbccbad
abc

خروجی نمونه ۱

3
7
0
1
14