#include "bits/stdc++.h"
using namespace std;

// Source: bqi343+Me
// Tested On:
// Fast prime sieve in O(NloglogN)
// Also finds the number of primes <= x
template <int N = 100007>
struct Sieve {
  bitset<N> isPrime;
  vector<int> primes, cum;
  Sieve() {
    isPrime.set();
    isPrime[0] = isPrime[1] = 0;
    for (int i = 4; i < N; i+=2) isPrime[i] = 0;
    for (int i = 3; i*i < N; i+=2)
      if (isPrime[i])
        for (int j = i*i; j < N; j += 2*i)
          isPrime[j] = 0;
    for (int i = 0; i < N; i++) {
      if (isPrime[i])
        primes.push_back(i);
      cum.push_back(primes.size());
    }
  }
};

template<char START = 'a', int ALPHABET=26>
struct SuffixAutomaton {
  struct State {
    int len;
    int link;
    int cnt;
    int next[ALPHABET];

    State() {
      memset(next,-1,sizeof(next));
    }
  };

  vector<State> states;
  int last;
  string s;

  SuffixAutomaton() {
    init();
  }

  SuffixAutomaton(string _s):s(_s) {
    init();
    for (char c : s)
      extend(c);
  }
  
  void init() {
    states.push_back(State());
    last = states[0].len = 0;
    states[0].link = -1;
  }

  void extend(char c) {
    assert(c >= START && c < START+ALPHABET);
    int k = states.size(),p;
    states.push_back(State());
    int idx = c-START;
    states[k].len = states[last].len+1;
    if (k != 0)
      states[k].cnt = 1;
    for (p = last; p != -1 && states[p].next[idx] < 0; p = states[p].link)
      states[p].next[idx]=k;
    if (p==-1) {
      states[k].link = 0;
    }
    else
    {
      int q = states[p].next[idx];
      if (states[p].len+1==states[q].len) {
        states[k].link = q;
      }
      else
      { 
        int w = states.size();;
        states.push_back(State());
        states[w].len = states[p].len+1;
        states[w].cnt = 0;
        for (int i =0; i < ALPHABET; i++) 
          states[w].next[i] = states[q].next[i];
        states[w].link = states[q].link;
        for (;p!=-1 && states[p].next[idx] == q; p = states[p].link)states[p].next[idx] = w;
        states[q].link = states[k].link = w;
      }
    }
    last = k;
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  Sieve<> S;
  int tt;
  cin >> tt;
  while(tt--) {
    string s;
    cin >> s;
    SuffixAutomaton<> SAM(s);
    auto& states = SAM.states;
    vector<pair<int,int>> state_lens;
    for (int state_idx =0; state_idx < states.size(); state_idx++)
      state_lens.push_back({states[state_idx].len,state_idx});
    sort(state_lens.begin(),state_lens.end(),greater<pair<int,int>>());
    for (auto& [_,state] : state_lens) {
      int link = states[state].link;
      if (link == -1) continue;
      states[link].cnt += states[state].cnt;
    }
    int ans =0;
    vector<int> state_cnt(states.size()), deg(states.size());
    state_cnt[0] = 1;
    for (int state = 0; state < states.size(); state++) {
      for (int i = 0; i < 26; i++) {
        int nxt = states[state].next[i];
        if (nxt != -1) deg[nxt]++;
      }
    }
    queue<int> q;
    q.push(0);
    while(!q.empty()) {
      int u = q.front();
      q.pop();
      for (int i =0; i < 26; i++) {
        int nxt = states[u].next[i];
        if (nxt != -1) {
          deg[nxt]--;
          state_cnt[nxt] += state_cnt[u];
          if (deg[nxt] == 0)
            q.push(nxt);
        }
      }
    }
    for (int state = 1; state < states.size(); state++) {
      if (S.isPrime[states[state].cnt])
        ans += state_cnt[state];
    }
    cout << ans << '\n';
  }
}
// String of words
// Number of distinct dtrings that occur a prime number of times