SUBS - String it out


Let A and B be two strings made up of alphabets such that A = A[1-n], B = B[1-m]. We say B is a subsequence of A if there exists a sequence of indices i1 < i2 <..m of A such that A[ik] = B[k].

Given B[1-m], 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 kth line should be the value of M for the kth pair of X and Y.

Example

Input:
3
abc
aabbcc
abc
bbccc
abcdef
abc

Output:
2
0
0


hide comments
Abhinav Gupta: 2017-09-09 08:25:16

Getting TLE even after applying binary search.

me_milan_11: 2017-08-24 20:51:56

AC in first attempt.. :D good question

baadshah_: 2016-07-06 14:23:22

AC in 1st Go!!
Nice Problem!!

kiwi1995: 2016-07-04 17:04:11

AC in 1ST go :D

Last edit: 2016-07-05 12:52:35
hash7: 2016-05-23 20:09:20

nope characters are not in lexicographic manner

xMAn: 2015-08-18 06:37:35

are characters in lexicographic order?

Rydel Dcosta: 2015-06-29 22:30:05

Awesome application of binary search :)

i_am_looser: 2015-06-10 18:07:55

Easy using binary search... ; )

Rahul Lingala: 2014-12-10 17:38:01

@thewatch
abc is a subsequence of aaabbzbccc

thewatch: 2014-09-02 20:20:55

is abc a subsequence of aaabbzbccc


Added by:Kashyap KBR
Date:2005-12-12
Time limit:4.823s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET