#include <bits/stdc++.h> using namespace std; using ll = long long; long long readInt(long long l,long long r,char endd){ long long x=0; int cnt=0; int fi=-1; bool is_neg=false; while(true){ char g=getchar(); if(g=='-'){ assert(fi==-1); is_neg=true; continue; } if('0'<=g && g<='9'){ x*=10; x+=g-'0'; if(cnt==0){ fi=g-'0'; } cnt++; assert(fi!=0 || cnt==1); assert(fi!=0 || is_neg==false); assert(!(cnt>19 || ( cnt==19 && fi>1) )); } else if(g==endd){ if(is_neg){ x= -x; } assert(l<=x && x<=r); return x; } else { assert(false); } } } string readString(int l,int r,char endd){ string ret=""; int cnt=0; while(true){ char g=getchar(); assert(g!=-1); if(g==endd){ break; } cnt++; ret+=g; } assert(l<=cnt && cnt<=r); return ret; } long long readIntSp(long long l,long long r){ return readInt(l,r,' '); } long long readIntLn(long long l,long long r){ return readInt(l,r,'\n'); } string readStringLn(int l,int r){ return readString(l,r,'\n'); } string readStringSp(int l,int r){ return readString(l,r,' '); } long long P10(int x){ return x == 0 ? 1 : 10 * P10(x - 1); } template <typename T, typename R = long long> vector<T> readArr(int len, R l, R r){ vector<T> a(len); for(int i = 0; i < len; i++){ if(i + 1 < len){ a[i] = readIntSp(l, r); } else { a[i] = readIntLn(l, r); } } return a; } struct suffix_aut { vector<map<int,int>> to; vector<int> len, link, cnt; int get_node(){ to.emplace_back(); len.emplace_back(); link.emplace_back(); cnt.emplace_back(); return (int)to.size() - 1; } int last; suffix_aut(){ get_node(); link[0] = -1; last = 0; } int adj(int u, int c){ auto it = to[u].find(c); if(it == to[u].end()) return -1; return it->second; } void extend(int c){ int cur = get_node(), p; len[cur] = len[last] + 1; cnt[cur] = 1; for(p = last; p != -1 && adj(p, c) == -1; p = link[p]) to[p][c] = cur; if(p == -1) link[cur] = 0; else { int q = to[p][c]; if(len[p] + 1 == len[q]) link[cur] = q; else { int cln = get_node(); to[cln] = to[q]; len[cln] = len[p] + 1; link[cln] = link[q]; link[q] = cln; link[cur] = cln; for(; p != -1 && adj(p, c) == q; p = link[p]) to[p][c] = cln; } } last = cur; } void augment(){ int sz = len.size(); vector<int> deg(sz, 0); for(int i = 1; i < sz; i++) deg[link[i]]++; queue<int> q; for(int i = 1; i < sz; i++) if(deg[i] == 0) q.push(i); while(!q.empty()){ int u = q.front(); q.pop(); if(link[u]){ cnt[link[u]] += cnt[u]; if(--deg[link[u]] == 0) q.push(link[u]); } } } }; int main(){ int t = readIntLn(1, P10(3)); int sum_n = 0; while(t--){ int n = readIntLn(1, P10(5)); sum_n += n; string A = readStringLn(n, n); string B = readStringLn(n, n); for(auto c : A) assert(c == '0' || c == '1'); for(auto c : B) assert(c == '0' || c == '1'); suffix_aut suf; for(auto c : A) suf.extend(c); int ans = 0, len = 0, cur = 0; for(auto c : B){ int nxt; while(cur != -1 && (nxt = suf.adj(cur, c)) == -1){ cur = suf.link[cur]; len = suf.len[cur]; } if(nxt == -1){ cur = 0; len = 0; } else { cur = nxt; len += 1; } ans = max(ans, len); } cout << ans << '\n'; } assert(1 <= sum_n && sum_n <= 5 * P10(5)); return 0; }