main.cc

#include <cmath>
#include <cassert>
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

bool is_subseq(const string &str2, const string &str1) {
	int m = str1.size();
	int n = str2.size();
	int j = 0;
	for (int i=0; i<n&&j<m; i++)
		if (str1[j] == str2[i])
			j++;
	return (j==m);
}

string string_pow(const string &s, int n) {
	stringstream ss;

	for (int i = 0; i < s.size(); i++) {
		for (int j = 0; j < n; j++) {
			ss << s[i];
		}
	}

	return ss.str();
}

int gustavo(const string &h, const string &n) {
	int max = ceil(h.size() / n.size());
	int left = 1;
	int right = max;
	int result = 0;

	while (left <= right) {
		int mid = (left + right) / 2;
		if (is_subseq(h, string_pow(n, mid))) {
			result = mid;
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}

	return result;
}

int main() {
	int T;
	cin >> T;
	string h, n;

	while (T--) {
		cin >> h >> n;
		cout <<  gustavo(h, n) << endl;
	}

	return 0;
}