DIVSTR - Divisible Strings


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|≤104)

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

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

hide comments
vineetjai: 2020-09-06 08:00:03

Don't use two different types of input methods like cin for test case and getline for the string.

sachit9_: 2020-02-21 17:58:39

wrong ans on test case 25 , can anyone help ??

amanharitsh: 2019-01-20 12:03:27

Hint: Don't think about the tag(Greedy) , this a adhoc problem with only one answer possible(so called minimum number).

ayushgupta1997: 2018-06-15 17:44:20

easy-peasy first find all corner cases :)

syam27: 2018-05-31 18:15:33

Nice one

boemogensen: 2018-05-25 05:02:22

thank you very much @shakuniiii

shakuniiii: 2018-05-24 22:56:37

@boemogensen http://www.cplusplus.com/reference/string/string/getline/

boemogensen: 2018-05-24 09:44:15

Hi all! Do you know how to read a string but the length of string is 0? . Thank You


Added by:MRM
Date:2018-05-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:SBU Newbies Programming Contest 2018