## Đáp án bài 5,6,9,A
### Bài 5

### Bài 6

#include <bits/stdc++.h>
using namespace  std;
long long n,a[15][(int)(2e4+5)],t,maxx=0,ans;
int main(){
//  a tự thêm freopen  
	cin >> t;
	while(t--){
		maxx=0, ans=0;
		cin >> n; 
		for(int i=1; i<=n; i++){
			cin >> a[t][i];
			maxx=max(maxx,a[t][i]);
		}
		for(int i=1; i<=n; i++){
			ans=max(a[t][i]%maxx,ans);
		}
		cout << ans << '\n';
	}
}

### Bài 9

#include <bits/stdc++.h>
using namespace  std;
bool f[(int)(1e7+2)];
long long n,l,r,ans,t,mid;
int main(){
//	freopen("BAI9.EASY.INP","r",stdin);
//	freopen("BAI9.EASY.OUT","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	for(int i=1; i<=1e7; i++) f[i]=true;
	f[1]=false; f[0]=false;
	for(int i=2; i*i<=1e7; i++){
		if(f[i]==true){
			for(int j=i*i; j<=1e7; j+=i) f[j]=false;
		}
	}
	cin >> t;
	while(t--){
		cin >> n;
		while(n--){
			if(f[n]==true){
				cout << n << '\n';
				break;
			}
		}
	}
}
	

### Bài A

#include <bits/stdc++.h>
using namespace  std;
long long h,ans;
string a,b;
int main(){
	freopen("BAIA.CLONE.INP","r",stdin);
	freopen("BAIA.CLONE.OUT","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	getline(cin,a);
	getline(cin,b);
	h=0;
	for(int i=0; i<a.size(); i++){
		if(a[i]==b[h]) ans++,h++;
		if(h==b.size()) h=0;
	}
	cout << (ans/(b.size()))*b.size();
}

### Bài B

#include<bits/stdc++.h>
using namespace std;
vector<int>a;
vector<int>b;
int dem[5];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    long long n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        long long x;
        cin>>x;
        if(x==0)dem[x]++;
        if(x<0)
            b.emplace_back(x);
        else
            a.emplace_back(x);
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end(),greater<int>());
    long long res=0;
    if(k%2==1)
    {
        res+=a[a.size()-1];
        k--;
        a.pop_back();
    }
    while(k>0)
    {
        long long phu1=0,phu2=0,phu3=0;
        if(a.size()>1)
            phu1=a[a.size()-1]+a[a.size()-2];
        if(b.size()>1)
            phu2=abs(b[b.size()-1])+abs(b[b.size()-2]);
        if(dem[0]>0)
            phu3=abs(b[b.size()-1]);
        if(max({phu1,phu2,phu3})==phu1)
        {
            a.pop_back();
            a.pop_back();
        }
        else if(max({phu1,phu2,phu3})==phu2)
        {
            b.pop_back();
            b.pop_back();
        }
        else
        {
            b.pop_back();
            dem[0]--;
        }
        res+=max({phu1,phu2,phu3});
        k-=2;
    }
    cout<<res;

}
//code a e nhát sửa quá =))

## Bonus
### Code lấy từ web cấm a nhớ sửa nha...
## Bài C

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
const int N = 2e5;
ll n, k, x;
ll c[N + 4], kt[N + 4];
pair <ll, ll> step[N + 4];
ll d[N + 4];
ll low, high, z = 0;
int main() {
	freopen("BAIC.ASTEPBACKBSTEPSFORWARD.INP", "r", stdin);
	freopen("BAIC.ASTEPBACKBSTEPSFORWARD.OUT", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> k >> x;
	for (int i = 1; i <= n; i ++) {
		cin >> c[i];
	}
	for (int i = 1; i <= n; i ++) {
		cin >> kt[i];
	}
	for (int i = 1; i <= k; i ++) {
		cin >> step[i].fi >> step[i].se;
	}
	for (int i = 1; i <= N; i ++)
		d[i] = -1e9;
	d[x] = c[x];
 	for (int i = x; i <= n; i ++) {
 		if (kt[i] == 1 && d[i] != -1e9)
 			continue;
		for (int j = 1; j <= k; j ++) {
			low = i - step[j].fi;
			high = i - step[j].fi + step[j].se;
			 if (low >= 1 && high <= n && kt[low] == 0 && kt[high] == 0) {
//	 			cout  << i << " " << low << " " << high << " \n";	
 				d[high] = max(d[high], d[i] + c[high] + c[low]);
			}
		}
//		cout << d[i] + c[n] << "\n";
		if (i != n)
			d[n] = max(d[n], d[i] + c[n]);
//		cout << "\n";
	}
	cout << d[n];
}