Znzryb's Blog

ABC-403-E - Forbidden Prefix

Posted on 2025-05-02 Edited on 2026-02-16

思路讲解

也是体验了一把学霸的感觉，一编译就本地AC，然后交上去就一次AC了。

比那个D题还要顺，只能说我的字符串哈希还是比较熟练的。

这个如果Hx里有比该前缀更小的单元，直接放弃。

FOR(i,0,SZ(s)-1){
	hax+=s[i]*Base[i];
	// 如果Hx里有比该前缀更小的单元，直接放弃
	if(Hx.find(hax)!=Hx.end()){
		needOp=false;
		break;
	}
}

AC代码

https://atcoder.jp/contests/abc403/submissions/65404782

源代码

// Problem: E - Forbidden Prefix
// Contest: AtCoder - AtCoder Beginner Contest 403
// URL: https://atcoder.jp/contests/abc403/tasks/abc403_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,K,Q,T;
set<arr> g[MAXN];
bool vis[MAXN];
ll Base[MAXN];

// 自然溢出取模

inline void solve(){
	cin>>Q;
	set<ll> Hx;
	Base[0]=1;
	FOR(i,1,MAXN/2){
		Base[i]=Base[i-1]*131;
	}
	ll ans=0;
	FOR(q,1,Q){
		ll t;string s;
		cin>>t>>s;
		// the number of strings in Y that have no element of X as a prefix
		if(t==1){
			ll hax=0;
			bool needOp=true;
			FOR(i,0,SZ(s)-1){
				hax+=s[i]*Base[i];
				// 如果Hx里有比该前缀更小的单元，直接放弃
				if(Hx.find(hax)!=Hx.end()){
					needOp=false;
					break;
				}
			}
			ll len=SZ(s);
			if(needOp){
				auto itb=g[len-1].lower_bound({hax,0});
				auto ite=g[len-1].lower_bound({hax,INF});
				for(auto it=itb;it!=ite;++it){
					ll que=(*it)[1];
					if(vis[que]) continue;
					vis[que]=true;
					--ans;
				}
				Hx.insert(hax);
			}
			cout<<ans<<"\n";
		}else{
			ll hax=0;
			bool needAdd=true;
			FOR(i,0,SZ(s)-1){
				hax+=s[i]*Base[i];
				if(Hx.find(hax)!=Hx.end()){
					needAdd=false;
					break;
				}
			}
			if(needAdd){
				++ans;
				ll hax=0;
				FOR(i,0,SZ(s)-1){
					hax+=s[i]*Base[i];
					g[i].insert({hax,q});
				}
			}
			cout<<ans<<"\n";
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*

*/

心路历程（WA，TLE，MLE……）

ABC-403-D - Forbidden Difference

Posted on 2025-05-02 Edited on 2026-02-16

思路讲解

这道题目，可以通过转化，变为给你一张链图，问你如何删去权重之和最少的点，使这张链图完全不联通。

这个问题可以通过dp解决。

dp[0][0]=0,dp[0][1]=ls.front();
FOR(j,1,SZ(ls)-1){
	// 当前带着的=之前不带的 之前带着砍掉之前带着的
	dp[j][0]=min({dp[j-1][1],dp[j-1][0]+ls[j-1]});
	// 当前不带=   之前带着砍掉当前      之前不带砍掉当前
	dp[j][1]=min(dp[j-1][0]+ls[j],dp[j-1][1]+ls[j]);
}
ans+=min(dp[SZ(ls)-1][0],dp[SZ(ls)-1][1]);

AC代码

https://atcoder.jp/contests/abc403/submissions/65403420

源代码

// Problem: D - Forbidden Difference
// Contest: AtCoder - AtCoder Beginner Contest 403
// URL: https://atcoder.jp/contests/abc403/tasks/abc403_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,D,K,T,A[MAXN];
// arr uA[MAXN];
ll Cnt[MAXN];
ll vis[MAXN];
ll dp[MAXN][2];

inline void solve(){
	cin>>N>>D;
	// list<ll> ls;
	FOR(i,1,N){
		cin>>A[i];
		++Cnt[A[i]];
		// ls.pb(A[i]);
	}
	// assert(D!=0);
	if(D==0){
		ll ans=0;
		FOR(i,0,MAXN-5){
			if(Cnt[i]) ++ans;
		}
		cout<<N-ans<<"\n";
		return;
	}
	// ll up=-INF,idx=0;
	// FOR(i,1,N){
		// if(up!=A[i]){
			// uA[++idx][0]=A[i];
			// uA[idx][1]=1;
			// up=A[i];
		// }else{
			// ++uA[A[i]][1];
		// }
	// }
	ll ans=0;
	FOR(i,0,MAXN-1-D){
		if(Cnt[i]==0) continue;
		if(Cnt[i+D]==0) continue;
		if(vis[i]) continue;
		vector<ll> ls;
		for(int j=i;j<=MAXN-1;j+=D){
			if(Cnt[j]) ls.pb(Cnt[j]),vis[j]=true;
			else break;
		}
		// ll oddC=0,evenC=0;
		// FOR(j,0,SZ(ls)-1){
			// if(j%2==0) evenC+=ls[j];
			// else oddC+=ls[j];
		// }
		// ans+=min(oddC,evenC);
		
		// dp[][0]表示带着这个（序号为i）的最小，dp1表示不带这个的最小消耗
		dp[0][0]=0,dp[0][1]=ls.front();
		FOR(j,1,SZ(ls)-1){
			// 当前带着的=之前不带的 之前带着砍掉之前带着的
			dp[j][0]=min({dp[j-1][1],dp[j-1][0]+ls[j-1]});
			// 当前不带=   之前带着砍掉当前      之前不带砍掉当前
			dp[j][1]=min(dp[j-1][0]+ls[j],dp[j-1][1]+ls[j]);
		}
		ans+=min(dp[SZ(ls)-1][0],dp[SZ(ls)-1][1]);
	}
	ans=min(ans,N);
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC 
https://atcoder.jp/contests/abc403/submissions/65403420
*/

心路历程（WA，TLE，MLE……）

WA，最后发现是循环范围出了问题

源代码

// Problem: D - Forbidden Difference
// Contest: AtCoder - AtCoder Beginner Contest 403
// URL: https://atcoder.jp/contests/abc403/tasks/abc403_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,D,K,T,A[MAXN];
// arr uA[MAXN];
ll Cnt[MAXN];
ll vis[MAXN];
ll dp[MAXN][2];

inline void solve(){
	cin>>N>>D;
	// list<ll> ls;
	FOR(i,1,N){
		cin>>A[i];
		++Cnt[A[i]];
		// ls.pb(A[i]);
	}
	// assert(D!=0);
	if(D==0){
		ll ans=0;
		FOR(i,0,MAXN-5){
			if(Cnt[i]) ++ans;
		}
		cout<<N-ans<<"\n";
		return;
	}
	// ll up=-INF,idx=0;
	// FOR(i,1,N){
		// if(up!=A[i]){
			// uA[++idx][0]=A[i];
			// uA[idx][1]=1;
			// up=A[i];
		// }else{
			// ++uA[A[i]][1];
		// }
	// }
	ll ans=0;
	FOR(i,0,MAXN-1-D){
		if(Cnt[i]==0) continue;
		// if(Cnt[i+D]==0) continue;
		if(vis[i]) continue;
		vector<ll> ls;
		for(int j=i;j<=MAXN-1-D;j+=D){
			if(Cnt[j]) ls.pb(Cnt[j]),vis[j]=true;
			else break;
		}
		// ll oddC=0,evenC=0;
		// FOR(j,0,SZ(ls)-1){
			// if(j%2==0) evenC+=ls[j];
			// else oddC+=ls[j];
		// }
		// ans+=min(oddC,evenC);
		
		// dp[][0]表示带着这个（序号为i）的最小，dp1表示不带这个的最小消耗
		dp[0][0]=0,dp[0][1]=ls.front();
		FOR(j,1,SZ(ls)-1){
			// 当前带着的=之前不带的 之前带着砍掉之前带着的
			dp[j][0]=min({dp[j-1][1],dp[j-1][0]+ls[j-1]});
			// 当前不带=   之前带着砍掉当前      之前不带砍掉当前
			dp[j][1]=min(dp[j-1][0]+ls[j],dp[j-1][1]+ls[j]);
		}
		ans+=min(dp[SZ(ls)-1][0],dp[SZ(ls)-1][1]);
	}
	ans=min(ans,N);
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*

*/

CF-1022-C. Neo's Escape

Posted on 2025-05-02 Edited on 2026-02-16

思路讲解

就是要注意到，如果一段连续的相同的数字是不会影响结果的，因此需要把他们缩减。

AC代码

源代码

// Problem: C. Neo's Escape
// Contest: Codeforces - Codeforces Round 1022 (Div. 2)
// URL: https://codeforces.com/contest/2108/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,2> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,K,T,A[MAXN],uA[MAXN];
// unordered_map<ll,ll> Pos;

inline void solve(){
	cin>>N;
	set<ll> reaches;
	// Pos.clear();
	A[0]=0,A[N+1]=0;
	priority_queue<arr> pq;
	FOR(i,1,N){
		cin>>A[i];
		// pq.push({A[i],i});
	}
	
	ll idx=0,up=0;
	FOR(i,1,N){
		if(up!=A[i]){
			up=A[i];
			uA[++idx]=A[i];
			pq.push({A[i],idx});
		}
	}
	ll ans=0;
	while(!pq.empty()){
		ll pos=pq.top()[1];
		pq.pop();
		if(reaches.find(pos)==reaches.end()){
			++ans;
			reaches.insert(pos+1);
			reaches.insert(pos-1);
		}else{
			reaches.insert(pos+1);
			reaches.insert(pos-1);
		}
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC https://codeforces.com/contest/2108/submission/318060392
*/

心路历程（WA，TLE，MLE……）

https://codeforces.com/contest/2108/submission/317973413

1
3
11 10 10

Edu-CF-178-E. Unpleasant Strings

Posted on 2025-04-30 Edited on 2026-02-16

思路讲解

首先贪心的，我们在每个位置上总归想跳的最远，且在每个位置上都跳的最远，得到的一定是最少跳跃次数的。

那么这个每个位置上通过加一个字母能够一次跳到的最远位置怎么得到的那？其实就是所有合法字母中上一次出现的位置最远的字母的位置（如果有一个合法字母前面没出现过，那我们就认为他直接跳出去结束了）。

ROF(i,N-1,0){
	FOR(j,0,K-1){
		if(Pos[j].empty()){
			JumpFar[i]=N;
			JumpCh[i][j]=N;
		}else{
			JumpFar[i]=max(Pos[j].back(),JumpFar[i]);
			JumpCh[i][j]=Pos[j].back();
		}
	}
	Pos[S[i]-'a'].pb(i);
}

然后知道了在这个位置上最远能跳多远，那么我们知道最多要跳多少次那？可以通过记忆化搜索。

ll dfs(ll x){
	if(x>=N) return 0;
	if(dp[x]!=0) return dp[x];
	return dfs(JumpFar[x])+1;
}

	ROF(i,N-1,0){
		dp[i]=dfs(i);
	}

最后这个串需要用多少位原串需要跳跃处理，否则会 $TLE$ ，最坏 $O(NQ)$ 时间复杂度。

AC代码

https://codeforces.com/contest/2104/submission/317799371

源代码

// Problem: E. Unpleasant Strings
// Contest: Codeforces - Educational Codeforces Round 178 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2104/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,Q,K,T;
char S[MAXN];
// ll Cnt[MAXN][35];
ll JumpFar[MAXN];
ll JumpCh[MAXN][35];
ll dp[MAXN];
vector<ll> Pos[35];

ll dfs(ll x){
	if(x>=N) return 0;
	if(dp[x]!=0) return dp[x];
	return dfs(JumpFar[x])+1;
}


inline void solve(){
	cin>>N>>K;
	FOR(i,0,N-1){
		cin>>S[i];
		// ++Cnt[S[i]-'a'];
	}
	// ROF(i,N-1,0){
		// FOR(j,0,30){
			// Cnt[i][j]=Cnt[i+1][j];
		// }
		// ++Cnt[i][S[i-1]-'a'];
	// }
	
	// JumpFar[N-1]=1;
	// Pos[S[N-1]-'a'].pb(N-1);
	ROF(i,N-1,0){
		FOR(j,0,K-1){
			if(Pos[j].empty()){
				JumpFar[i]=N;
				JumpCh[i][j]=N;
			}else{
				JumpFar[i]=max(Pos[j].back(),JumpFar[i]);
				JumpCh[i][j]=Pos[j].back();
			}
		}
		Pos[S[i]-'a'].pb(i);
	}
	ROF(i,N-1,0){
		dp[i]=dfs(i);
// #ifdef LOCAL
    // cerr << "i:"<<i<<" dp:"<<dp[i] << '\n';
// #endif
	}
	
// #ifdef LOCAL
    // FOR(i,0,N-1){
    	// cerr<<dp[i]<<" ";
    // }
    // cerr<<"\n";
// #endif

	cin>>Q;
	while(Q--){
		// 要在末尾加几个合法字母，才能让这个字符串s不是S的子集
		string s;
		cin>>s;
		if(SZ(s)>N){
			cout<<0<<"\n";
			continue;
		}
		ll idx=0,idxs=0,bp=-INF;
		while(idxs<N){
			if(idx>=SZ(s)) {
				break;
			}
			// assert(idx<SZ(s));
			if(s[idx]==S[idxs]){
				bp=idxs;
				++idx;
				idxs=JumpCh[idxs][s[idx]-'a'];
			}else{
				idxs=JumpCh[idxs][s[idx]-'a'];
			}
		}
		if(idx<SZ(s)){
			cout<<"0\n";
			continue;
		}
		
// #ifdef LOCAL
    // cerr << "Q: "<<Q<<" bp:"<<bp<<" idx:"<<idx << '\n';
// #endif

		cout<<dp[bp]<<"\n";
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/2104/submission/317799371
*/

心路历程（WA，TLE，MLE……）

https://codeforces.com/contest/2104/submission/317796467

对比对部分没有优化。

源代码

// Problem: E. Unpleasant Strings
// Contest: Codeforces - Educational Codeforces Round 178 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2104/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,Q,K,T;
char S[MAXN];
ll Cnt[MAXN][35];
ll JumpFar[MAXN];
ll dp[MAXN];
vector<ll> Pos[35];

ll dfs(ll x){
	if(x>=N) return 0;
	if(dp[x]!=0) return dp[x];
	return dfs(JumpFar[x])+1;
}

inline void solve(){
	cin>>N>>K;
	FOR(i,0,N-1){
		cin>>S[i];
		// ++Cnt[S[i]-'a'];
	}
	// ROF(i,N-1,0){
		// FOR(j,0,30){
			// Cnt[i][j]=Cnt[i+1][j];
		// }
		// ++Cnt[i][S[i-1]-'a'];
	// }
	
	// JumpFar[N-1]=1;
	// Pos[S[N-1]-'a'].pb(N-1);
	ROF(i,N-1,0){
		FOR(j,0,K-1){
			if(Pos[j].empty()){
				JumpFar[i]=N;
				break;
			}else{
				JumpFar[i]=max(Pos[j].back(),JumpFar[i]);
			}
		}
		Pos[S[i]-'a'].pb(i);
	}
	ROF(i,N-1,0){
		dp[i]=dfs(i);
#ifdef LOCAL
    cerr << "i:"<<i<<" dp:"<<dp[i] << '\n';
#endif
	}
	
#ifdef LOCAL
    FOR(i,0,N-1){
    	cerr<<dp[i]<<" ";
    }
    cerr<<"\n";
#endif

	cin>>Q;
	while(Q--){
		// 要在末尾加几个合法字母，才能让这个字符串s不是S的子集
		string s;
		cin>>s;
		if(SZ(s)>N){
			cout<<0<<"\n";
			continue;
		}
		ll idx=0,bp=-INF;
		FOR(i,0,N-1){
			if(idx>=SZ(s)) {
				break;
			}
			// assert(idx<SZ(s));
			if(s[idx]==S[i]){
				bp=i;
				++idx;
			}
		}
		if(idx<SZ(s)){
			cout<<"0\n";
			continue;
		}
#ifdef LOCAL
    cerr << "Q: "<<Q<<" bp:"<<bp<<" idx:"<<idx << '\n';
#endif
		cout<<dp[bp]<<"\n";
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*

*/

Edu-CF-178-D. Array and GCD

Posted on 2025-04-29 Edited on 2026-02-16

思路讲解

其实思路还是很简单的，就是符合要求的一列数字，数字总和最小的就是 $2，3，5，7，11，…$

这样的一串素数数列。

证明？那么我们假设其中一个数字可以减去1，首先2不能-1（出现了1），那么其他的数字-1也不能（被2除）。

得证。

AC代码

https://codeforces.com/contest/2104/submission/317754416

源代码

// Problem: D. Array and GCD
// Contest: Codeforces - Educational Codeforces Round 178 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2104/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(4e5)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr ll range=static_cast<ll>(7e6)+5;

ll N,M,T,A[MAXN];
ll isPrime[range+10];
vector<ll> primes;
ll primeSum[MAXN];

inline void genPrime(){
	FOR(i,2,range) {isPrime[i]=true;}
	// range 范围内经过估算，有4.4e5个素数
	for(int i=2;i*i<=range;++i){
		if(!isPrime[i]) continue;
		for(int j=2*i;j<=range;j+=i){
			isPrime[j]=false;
		}
	}
	for(int i=2;i<=range;++i){
		if(isPrime[i]) primes.pb(i);
	}
	// assert(SZ(primes)>MAXN);
}

inline bool check(ll x){
	if(x==N-1) return true;
	ll res=0;
	FOR(i,1+x,N){
		res+=A[i];
	}
	ll stand=0;
	ll len=N-x;
	if(len==2){
		stand=5;
	}else{
		FOR(i,0,len-1){
			stand+=primes[i];
		}
	}
	
// #ifdef LOCAL
    // cerr << "len:"<<N-x<<" stand:"<<stand << '\n';
// #endif
	if(res>=stand) return true;
	return false;
}

inline void solve(){
	cin>>N;
	FOR(i,1,N){
		cin>>A[i];
	}
	sort(A+1,A+1+N);
	ll l=0,r=N-1;
// #ifdef LOCAL
    // cerr << "OK1" << '\n';
// #endif
	while(l<r){
		ll mid=l+r>>1;
// #ifdef LOCAL
    // cerr << "OK2" << '\n';
// #endif
		if(check(mid)){
			r=mid;
		}else{
			l=mid+1;
		}
	}
	cout<<l<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	genPrime();
	while(T--){
		solve();
	}
	// solve();
	return 0;
}
/*
AC https://codeforces.com/contest/2104/submission/317754416

*/