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 >
	maxine: 2021-07-23 11:48:50 How abc is subsequence of aaabbzbccc?
	spathak: 2021-03-08 21:33:55 AC in 1st go lol so easy!! :-)
	xoker: 2020-04-17 23:14:26 Can someone tell me in first test case string (X)^0 ,( X)^1 and (X)^2 is also sub sequence of string Y?
	coolio_1: 2020-03-12 15:44:02 AC in 1 go!
	wingman__7: 2020-01-08 12:31:25 I really don't know how to solve it using binary search... I used hash map to get AC
	mujahid_3732: 2019-05-21 20:59:08 Easier one.. Ac in one go Not using binary search
	k0x3r: 2018-05-04 09:31:40 Though you get AC without binary search also, really appreciate beauty of problem.
	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!!