#![allow(non_upper_case_globals, unused_imports)]
#![allow(clippy::indexing_slicing)]

use std::cmp::{max, min};
use std::fmt::Debug;
use std::io::{self, BufRead, Write};

struct A {
    len: usize,
    s: [u8; sz],
    sa: [usize; sz],
    rk: [usize; sz << 1],
    height: [usize; sz],
    f: [[usize; log_num]; sz],
}

static mut sa: A = A {
    len: 0,
    s: [0; sz],
    sa: [0; sz],
    rk: [0; sz << 1],
    height: [0; sz],
    f: [[0; log_num]; sz],
};
static mut pa: A = A {
    len: 0,
    s: [0; sz],
    sa: [0; sz],
    rk: [0; sz << 1],
    height: [0; sz],
    f: [[0; log_num]; sz],
};

static mut oldrk: [usize; sz << 1] = [0; sz << 1];
static mut id: [usize; sz] = [0; sz];
static mut key: [usize; sz] = [0; sz];
static mut cnt: [usize; sz] = [0; sz];
static mut log: [usize; sz] = [0; sz];
static mut a: [i32; sz] = [0; sz];
static mut b: [i32; sz] = [0; sz];
static mut m: usize = 128;
const sz: usize = 30010;
const log_num: usize = 21;

fn main() {
    let stdin = io::stdin();
    let stdout = io::stdout();
    unsafe {
        solve(stdin.lock(), stdout.lock());
    }
}

unsafe fn solve<R, W>(mut input: R, mut output: W)
where
    R: BufRead,
    W: Write,
{
    let mut buf = String::new();
    input.read_line(&mut buf).unwrap();
    let arg: Vec<usize> = buf
        .split_whitespace()
        .map(|s| s.parse::<usize>().unwrap())
        .collect();
    log[2] = 1;
    for i in 3..sz {
        log[i] = log[i / 2] + 1;
    }
    for _ in 0..arg[0] {
        let mut buf = String::new();
        input.read_line(&mut buf).unwrap();
        if buf.ends_with('\n') {
            buf.pop();
        }
        if buf.ends_with('\r') {
            buf.pop();
        }
        let str = buf.into_bytes();
        let n = str.len();
        sa.len = n;
        pa.len = n;
        for i in 0..n {
            sa.s[i] = str[i];
            pa.s[i] = str[n - i - 1];
        }
        sa.init();
        pa.init();
        for len in 1..n / 2 + 1 {
            for pt1 in (len - 1..n - len).step_by(len) {
                let pt2 = pt1 + len;
                if pt2 >= n {
                    break;
                }
                let lcp = min(sa.find(pt1, pt2), len);
                let lcs = min(pa.find(n - pt2, n - pt1), len - 1);
                if lcp + lcs >= len {
                    let lap = lcp + lcs - len + 1;
                    b[pt1 - lcs] += 1;
                    b[pt1 - lcs + lap] -= 1;
                    a[pt2 + lcp - lap] += 1;
                    a[pt2 + lcp] -= 1;
                }
            }
        }
        for i in 1..n + 1 {
            a[i] += a[i - 1];
            b[i] += b[i - 1];
        }
        let mut result: u64 = 0;
        for i in 0..n - 1 {
            result += a[i] as u64 * b[i + 1] as u64;
        }
        writeln!(output, "{}", result).unwrap();
        a.fill(0);
        b.fill(0);
        sa.clear();
        pa.clear();
    }
}

impl A {
    unsafe fn init(&mut self) {
        let n = self.len;
        for i in 0..n {
            self.rk[i] = self.s[i] as usize;
            cnt[self.rk[i]] += 1;
        }
        for i in 1..m {
            cnt[i] += cnt[i - 1];
        }
        for i in (0..n).rev() {
            cnt[self.rk[i]] -= 1;
            self.sa[cnt[self.rk[i]]] = i;
        }
        let mut w = 1;
        let mut p;
        while w <= n {
            p = 0;
            for i in (n - w..n).rev() {
                id[p] = i;
                p += 1;
            }
            for i in self.sa.iter().take(n) {
                if *i >= w {
                    id[p] = *i - w;
                    p += 1;
                }
            }
            cnt.fill(0);
            for i in 0..n {
                key[i] = self.rk[id[i]];
                cnt[key[i]] += 1;
            }
            for i in 1..m {
                cnt[i] += cnt[i - 1];
            }
            for i in (0..n).rev() {
                cnt[key[i]] -= 1;
                self.sa[cnt[key[i]]] = id[i];
            }
            oldrk.copy_from_slice(&self.rk[..]);
            self.rk[self.sa[0]] = 0;
            p = 0;
            for i in 1..n {
                if !cmp(self.sa[i], self.sa[i - 1], w) {
                    p += 1;
                }
                self.rk[self.sa[i]] = p;
            }
            if p + 1 == n {
                for i in 0..n {
                    self.sa[self.rk[i]] = i;
                }
                break;
            }
            w <<= 1;
            m = p + 1;
        }
        for i in 0..n {
            self.rk[self.sa[i]] = i;
        }
        p = 0;
        for i in 0..n {
            if self.rk[i] == 0 {
                continue;
            }
            p = p.saturating_sub(1);
            while self.s[i + p] == self.s[self.sa[self.rk[i] - 1] + p] {
                p += 1;
            }
            self.height[self.rk[i]] = p;
        }
        m = 128;
        cnt.fill(0);
        oldrk.fill(0);
        id.fill(0);
        key.fill(0);

        for i in 0..n {
            self.f[i][0] = self.height[i];
        }
        for j in 1..log_num {
            let mut i = 0;
            while i + (1 << j) <= n {
                self.f[i][j] = min(self.f[i][j - 1], self.f[i + (1 << (j - 1))][j - 1]);
                i += 1;
            }
        }
    }
    unsafe fn find(&self, x: usize, y: usize) -> usize {
        let i = min(self.rk[x], self.rk[y]) + 1;
        let j = max(self.rk[x], self.rk[y]) + 1;
        let step = log[j - i];
        min(self.f[i][step], self.f[j - (1 << step)][step])
    }
    fn clear(&mut self) {
        self.f.fill([0; log_num]);
        self.sa.fill(0);
        self.rk.fill(0);
        self.height.fill(0);
        self.s.fill(0);
    }
}
unsafe fn cmp(x: usize, y: usize, w: usize) -> bool {
    oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w]
}
impl Debug for A {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        writeln!(f, "len: {}", self.len).unwrap();
        writeln!(f, "s: ").unwrap();
        write!(f, "[ ").unwrap();
        for i in self.s.iter().take(self.len) {
            write!(f, "{i} ").unwrap();
        }
        writeln!(f, "]").unwrap();
        writeln!(f, "sa: ").unwrap();
        write!(f, "[ ").unwrap();
        for i in self.sa.iter().take(self.len) {
            write!(f, "{i} ").unwrap();
        }
        writeln!(f, "]").unwrap();
        writeln!(f, "rk: ").unwrap();
        write!(f, "[ ").unwrap();
        for i in self.rk.iter().take(self.len) {
            write!(f, "{i} ").unwrap();
        }
        writeln!(f, "]")
    }
}