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 i₁ < i₂ <..m of A such that A[i_k] = B[k].

Given B[1-m], a string of characters from some alphabets, Bⁱ is defined as string with the characters of B each repeating i times. For example, (abbacc)³ = aaabbbbbbaaacccccc. Also, B⁰ 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 number 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 number 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

< Previous 1 2 Next >
	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
	Vijai Shankar Natarajan: 2011-06-26 10:28:31 "output limit exceeded". Your program has printed too much data to output (typically more than 25MB).
	vivek yadav: 2010-12-20 14:25:19 can any body describe about SIGXFSZ error. i have got first time this type error.