HIIT remains

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;

ll dp[101010][4];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tcs;
	cin>>tcs;
	for (int tc=0;tc<tcs;tc++) {
		string s;
		cin>>s;
		int n=s.size();
		if (s[0]=='H') dp[0][0]=1;
		else dp[0][0]=0;
		for (int i=1;i<n;i++) {
			for (int j=0;j<4;j++) dp[i][j]=dp[i-1][j];
			if (s[i]=='H') dp[i][0]++;
			if (s[i]=='I') {
				dp[i][1]+=dp[i-1][0];
				dp[i][2]+=dp[i-1][1];
			}
			if (s[i]=='T') dp[i][3]+=dp[i-1][2];
		}
		cout<<dp[n-1][3]<<"\n";
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED