#include <bits/stdc++.h>
#define N 5009
#define ull unsigned long long
using namespace std;
int n, a[N];
int f[N][N], g[N][N];

void handle(vector<int>vt, int len) {
	if (vt.size() == 1)
		return;
	vector<int>v[11];
	for (auto x : vt) {
		if (x - len >= 1)
			v[a[x - len]].push_back(x);
		else
			v[10].push_back(x);
	}
	for (int i = 0; i <= 10; i++) {
		for (int j = i + 1; j <= 10; j++) {
			for (auto x : v[i]) {
				for (auto y : v[j]) {
					f[x][y] = f[y][x] = len ;
				}
			}
		}
	}
	for (int i = 0; i < 10; i++)
		if (v[i].size())
			handle(v[i], len + 1);
}

struct {
	ull s[N], base, pw[N];
	void init(ull base1) {
		base = base1;
		pw[0] = 1;
		for (int i = 1; i <= n; i++) {
			s[i] = s[i - 1] * base + a[i] + 1;
			pw[i] = pw[i - 1] * base;
		}
	}
	ull query(int l, int r) {
		return s[r] - s[l - 1] * pw[r - l + 1];
	}
	bool eql(int x, int y, int len) {
		return query(x, x + len - 1) == query(y, y + len - 1);
	}
} hsh;
int h[N];

void solve() {
	string st;
	cin >> st;
	n = st.size();
	for (int i = 1; i <= n; i++)
		a[i] = st[i - 1] - '0';
	vector<int>v;
	for (int i = 1; i <= n; i++)
		v.push_back(i);
	handle(v, 0);
	hsh.init(131);
	/*
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++)
			cout << f[i][j] << " ";
		cout << endl;
	}*/
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			g[i][j] = g[i][j - 1];
			if (j <= i - 1 && i + j - 1 <= n)
				g[i][j] += hsh.eql(i - j, i, j);
			//cout << g[i][j] << " ";
		}
		//cout << endl;
	}
	long long ans = 0;
	for (int r = 1; r <= n; r++) {
		for (int i = 0; i <= n; i++)
			h[i] = 0;
		for (int i = r + 2; i <= n; i++)
			h[min(i - r - 1, f[r][i])]++;
		for (int i = n; i >= 0; i--)
			h[i] += h[i + 1];
		for (int l = r; l >= 1; l--) {
			ans += (long long)g[l][r - l] * h[r - l + 1];
			//if ((long long)g[l][r - l] * h[r - l + 1] != 0)cout << l << " " << r << " " << (long long)g[l][r - l] * h[r - l + 1] << endl;
		}
	}
	printf("%lld\n", ans);
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--)
		solve();
	return 0;
}
/*
4
114514
0000000
114514
0000000
*/