HIIT remains

#include <iostream>
#include <string>
#include <set>
#include <vector>

using namespace std;

typedef int64_t LL;

void solve(){
  string s; cin >> s;
  LL n = s.size();
  vector<LL> dp(4);
  for(LL i = 0; i < n; i++){
    if(s[i] == 'H') dp[0]++;
    if(s[i] == 'I'){
      dp[2] += dp[1];
      dp[1] += dp[0];
    }
    if(s[i] == 'T'){
      dp[3] += dp[2];
    }
  }
  cout << dp[3] << endl;
}

int main(){
  LL t; cin >> t;
  while(t--) solve();
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED