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 nonnegative 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^{4})
The second line contains string T consisting of lowercase English letters. (0<T≤10^{4})
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
amanharitsh:
20190120 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:
20180615 17:44:20
easypeasy first find all corner cases :) 

ganesh5:
20180601 09:55:00
Last edit: 20180601 09:55:46 

syam27:
20180531 18:15:33
Nice one


entcat:
20180526 15:30:21


boemogensen:
20180525 05:02:22
thank you very much @shakuniiii 

shakuniiii:
20180524 22:56:37
@boemogensen http://www.cplusplus.com/reference/string/string/getline/


boemogensen:
20180524 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:  20180523 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  SBU Newbies Programming Contest 2018 