SUBS  String it out
Given B[1m], a string of characters from some alphabets, B^i is defined as string with the characters of B each repeating i times. For example, (abbacc)^3 = aaabbbbbbaaacccccc. Also, B^0 is the empty string.
Given strings X, Y made up of characters from 'a'  'z' find the maximum value of M such that X^M is a subsequence of Y.
Input
 The first line of the input contains a positive integer t <= 20, denoting the no. of test cases.
 The following 2t lines contain the value of X and Y for the cases.
 The description of the test cases follow one after the other.
 Line 2k contains the value of X for case k; (1 <= k <= t)
 Line 2k+1 contains the value of Y for case k; (1 <= k <= t).
 The no. of characters in X , Y will be <= 500010.
Output
The output must contain t lines, each line corresponding to a test case. The value on the k^{th} line should be the value of M for the k^{th} pair of X and Y.
Example
Input:
3
abc
aabbcc
abc
bbccc
abcdef
abc
Output:
2
0
0
hide comments
mujahid_3732:
20190521 20:59:08
Easier one..


k0x3r:
20180504 09:31:40
Though you get AC without binary search also, really appreciate beauty of problem. 

Abhinav Gupta:
20170909 08:25:16
Getting TLE even after applying binary search. 

me_milan_11:
20170824 20:51:56
AC in first attempt.. :D good question 

baadshah_:
20160706 14:23:22
AC in 1st Go!!


kiwi1995:
20160704 17:04:11
AC in 1ST go :D Last edit: 20160705 12:52:35 

hash7:
20160523 20:09:20
nope characters are not in lexicographic manner


xMAn:
20150818 06:37:35
are characters in lexicographic order?


Rydel Dcosta:
20150629 22:30:05
Awesome application of binary search :) 

i_am_looser:
20150610 18:07:55
Easy using binary search... ; ) 
Added by:  Kashyap KBR 
Date:  20051212 
Time limit:  4.823s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 