// Level 37 - 崇高性(Sublimity)
#include <bits/stdc++.h>
using namespace std;
#define _rep(i_,a_,b_) for(int i_ = (a_); i_ <= (b_); ++i_)
#define mid ((L+R) >> 1)
#define multiCase() int testCnt = in(); _rep(curCase,1,testCnt)
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
#define pc __builtin_popcount
using ll = long long;
using pii = pair<int,int>;

int in(void) { int x; scanf("%d", &x); return x; } ll inl(void) { ll x; scanf("%lld", &x); return x; }
void out(int x) { printf("%d ", x); } void outln(int x) { printf("%d\n", x); }
void out(ll x) { printf("%lld ", x); } void outln(ll x) { printf("%lld\n", x); }
template<typename T> void chkmax(T &a, const T &b) { a = max(a, b); } 
template<typename T> void chkmin(T &a, const T &b) { a = min(a, b); } 
const int kN = 205000;
// int mu[kN], pri[kN], prime[kN], pcnt;
char s[kN]; int n;

struct SuffixArray {
	int sa[kN], x[kN], y[kN], rk[kN], cnt[kN], h[18][kN];
	void suffix_sort(char *s) {
		x[n + 1] = y[n + 1] = 0;
		int m = 500;
		_rep(i,1,m) cnt[i] = 0;
		_rep(i,1,n) ++cnt[x[i] = s[i]];
		_rep(i,1,m) cnt[i] += cnt[i - 1];
		_rep(i,1,n) sa[cnt[x[i]]--] = i;
		for(int k = 1; k <= n; k <<= 1) {
			int top = 0;
			_rep(i,n - k + 1, n) y[++top] = i;
			_rep(i,1,n) if(sa[i] > k) y[++top] = sa[i] - k;
			_rep(i,1,m) cnt[i] = 0;
			_rep(i,1,n) ++cnt[x[i]];
			_rep(i,1,m) cnt[i] += cnt[i - 1];
			for(int i = n; i; --i) sa[cnt[x[y[i]]]--] = y[i], y[i] = 0;
			swap(x, y);
			x[sa[1]] = m = 1;
			_rep(i,2,n) if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])
				x[sa[i]] = m; else x[sa[i]] = ++m;
		}
		_rep(i,1,n) rk[sa[i]] = i;
		int tmp = 0;
		_rep(i,1,n) {
			if(rk[i] == 1) continue;
			if(tmp) --tmp;
			while(s[i + tmp] == s[sa[rk[i] - 1] + tmp]) ++tmp;
			h[0][rk[i]] = tmp;
		}
		_rep(i,1,17) _rep(j,2,n - (1 << i) + 1) h[i][j] = min(h[i - 1][j], h[i - 1][j + (1 << i - 1)]);
	}
	int LCP(int i, int j) {
		if(i == j) return n - i + 1;
		int a = rk[i], b = rk[j];
		if(a > b) swap(a, b);
		int k = __lg(b - a);
		return min(h[k][a + 1], h[k][b - (1 << k) + 1]);
	}
} sa, as;
 
int ch[kN << 1][26], len[kN << 1], link[kN << 1], endpos[kN << 1], nc, last;
int clone(int x) { return ++nc, memcpy(ch[nc], ch[x], sizeof(ch[nc])), link[nc] = link[x], endpos[nc] = endpos[x], nc; }
void extend(char c, int a) { c -= 'a';
	int cur = ++nc; len[cur] = len[last] + 1, endpos[cur] = a;  memset(ch[cur], 0, sizeof(ch[cur]));
	while(~last && !ch[last][c]) ch[last][c] = cur, last = link[last];
	if(last == -1) link[cur] = 0;
	else {
		int p = ch[last][c];
		if(len[p] == len[last] + 1) link[cur] = p;
		else {
			int q = clone(p); len[q] = len[last] + 1;
			while(~last && ch[last][c] == p) ch[last][c] = q, last = link[last];
			link[cur] = link[p] = q;
		}
	} last = cur;
}
vector<int> nodes[kN];
vector<pii> scan[kN];

int lp[kN << 2];
void build(int x, int L, int R) {
	lp[x] = 1e9;
	if(L == R) return;
	build(x << 1, L, mid), build(x << 1 | 1, mid + 1, R);
}
void modify(int x, int L, int R, int p, int y) {
	if(L == R) {
		if(y < 0 && lp[x] == -y) lp[x] = 1e9;
		if(y > 0) lp[x] = y;
		return;
	}
	p <= mid ? modify(x << 1, L, mid, p, y) : modify(x << 1 | 1, mid + 1, R, p, y);
	lp[x] = min(lp[x << 1], lp[x << 1 | 1]);
}
pii query(int x, int L, int R, int p) {
	if(lp[x] > p) return make_pair(-1, -1);
	if(L == R) return make_pair(L, lp[x]);
	pii v = query(x << 1, L, mid, p);
	if(v != make_pair(-1, -1)) return v;
	return query(x << 1 | 1, mid + 1, R, p);
}
pii yreuq(int x, int L, int R, int p) {
	if(lp[x] > p) return make_pair(-1, -1);
	if(L == R) return make_pair(L, lp[x]);
	pii v = yreuq(x << 1 | 1, mid + 1, R, p);
	if(v != make_pair(-1, -1)) return v;
	return yreuq(x << 1, L, mid, p);
}
int main() {
	// freopen("string.in", "r", stdin);
	// freopen("string.out", "w", stdout);
	// mu[1] = 1; int N = 200000;
	// _rep(i,2,N) {
	// 	if(!pri[i]) prime[++pcnt] = i, mu[i] = -1;
	// 	for(int j = 1; j <= pcnt && i * prime[j] <= N; ++j) {
	// 		if(i % prime[j] == 0) {
	// 			mu[i * prime[j]] = 0;
	// 			pri[i * prime[j]] = 1;
	// 			break;
	// 		}
	// 		mu[i * prime[j]] = -mu[i];
	// 		pri[i * prime[j]] = 1;
	// 	}
	// }
	// _rep(i,1,10) debug("%d%c", mu[i], " \n"[i == 10]);
	multiCase() {
		// clock_t st = clock();
		scanf("%s", s + 1);
		n = strlen(s + 1);
		// suffix_sort();
		sa.suffix_sort(s);
		reverse(s + 1, s + 1 + n);
		as.suffix_sort(s);
		reverse(s + 1, s + 1 + n);
		nc = last = 0, memset(ch[0], 0, sizeof(ch[0])), len[0] = 0, link[0] = -1;
		_rep(i,1,n) extend(s[i], i); 
		_rep(i,1,n) nodes[i].clear();
		_rep(i,1,nc) nodes[endpos[i]].emplace_back(i);
		_rep(r,1,n) {
			debug("r = %d\n", r);
			for(auto &u : nodes[r]) {
				debug("Getnode (%d, %d, %d) {", u, len[link[u]], len[u]);
				_rep(l,len[link[u]] + 1, len[u]) {
					_rep(pos,endpos[u] - l + 1, endpos[u]) debug("%c", s[pos]);
					debug(",");
				}
				debug("}\n");
			}
		}
		_rep(i,1,n) scan[i].clear();
		_rep(a,1,n) {
			// int lastr = -1;
			for(int l = 1, r = a + 1; r <= n; l += a, r += a) {
				int lft = as.LCP(n - l + 1, n - r + 1), rgt = sa.LCP(l, r);
				// debug("a = %d, l = %d, r = %d, lft = %d, rgt = %d\n", a, l, r, lft, rgt);
				if(rgt > a || lft + rgt - 1 < a) continue;
				int L = l - lft + 1, R = r + rgt - 1;
				scan[L + 2 * a - 1].emplace_back(a, L);
				scan[R + 1].emplace_back(a, -L);
				// lastr = R;
				debug("Find [%d, %d], period = %d\n", L, R, a);
			}
		}
		// _rep(i,1,n) sort(scan[i].begin(), scan[i].end(), [](const pii &a, const pii &b) {
			// return a.second < b.second;
		// });
		ll ans = 0;
		_rep(i,1,nc) ans += len[i] - len[link[i]];
		debug("ans = %lld\n", ans);
		build(1, 1, n);
		_rep(r,1,n) {
			// debug("r = %d\n", r);
			for(auto &[a, b] : scan[r]) modify(1, 1, n, a, b); //, debug("MODIFY %d %d\n", a, b);
			for(auto &u : nodes[r]) {
				auto [period, pos] = query(1, 1, n, r - len[link[u]]);
				if(period == -1) continue;
				debug("Node %d gets %d, %d %d\n", u, period, pos, r - pos + 1);
				ans -= min(len[u], r - pos + 1) / period - len[link[u]] / period;
				if(len[link[u]] < period && period <= min(len[u], r - pos + 1)) ++ans;
				auto [p2, po2] = yreuq(1, 1, n, r - len[link[u]]);
				if(p2 != -1 && p2 % period != 0) {
					ans -= min(len[u], r - po2 + 1) / p2 - len[link[u]] / p2;
					if(len[link[u]] < p2 && p2 <= min(len[u], r - po2 + 1)) ++ans;
				}
				debug("ans = %lld\n", ans);
			}	
		}
		outln(ans);
		// debug("single test case time = %.2lf\n", (clock() - st) * 1. / CLOCKS_PER_SEC);
		// int x, y;
		// while(1) {
		// 	x = in(), y = in();
		// 	if(!x && !y) break;
		// 	outln(LCP(x, y));
		// }
	}
	return 0;
}