Background

Special for beginners, ^_^

Description

三核苷酸是组成DNA序列的基本片段。具体来说，核苷酸一共有4种，分别用’A’，’G’，’C’，’T’来表示。而三核苷酸就是由3个核苷酸排列而成的DNA片段。三核苷酸一共有64种，分别是’AAA’，’AAG’，…，’GGG’。给定一个长度为L的DNA序列，一共可以分辨出（L-2）个三核苷酸。现在我们想用一些统计学的方法来进行一些分析，步骤如下：

1. 对于这（L-2）个三核苷酸，我们从左到右给予编号，分别为1到L-2。
   

2. 从这（L-2）个三核苷酸挑选一对出来，一共有(L-2)*(L-3)/2种可能。如果某一对三核苷酸是一样的，我们就记录他们之间的距离。他们之间的距离定义为他们的编号之差。
   

3. 根据我们所记录的“样本数据”，我们现在需要计算样本数据的方差。方差的计算公式是S2=[(x ~1~ -X) ^ 2^ +(x ~2~ -X) ^ 2^ +…+(x ~n~ -X) ^2^ ]/n, X=(x ~1~ +x ~2~ +…+x ~n~ )/n。如果样本的大小n=0，那么我们认为S2=X=0。
   

例如，我们要统计DNA序列’ATATATA’：

1. 为三核苷酸编号. L ~1~ : ATA, L ~2~ :TAT, L ~3~ :ATA, L ~4~ :TAT, L ~5~ :ATA.
   

2. (L ~1~ ,L ~3~ )=2, (L ~1~ ,L ~5~ )=4, (L ~3~ ,L ~5~ )=2, (L ~2~ ,L ~4~ )=2. 所以样本数据是2,4,2,2.
   

3. 样本数据平均值X=(2+4+2+2)/4=2.5.
   

方差S2=[(2-2.5) ^2^ +(4-2.5) ^ 2^ +(2-2.5) ^2^ +(2-2.5) ^2^ ]/4=0.75.

给定一个DNA序列，请你计算出它的方差。

Format

Input

输入包含多组测试数据。第一行包含一个正整数T，表示测试数据数目。每组数据包含一个由’A’，’G’，’C’，’T’组成的字符串，代表要统计的DNA序列。DNA序列的长度大于等于3且不会超过100000。

Output

对每组测试数据，输出一行答案，为一个保留6位精度的实数，代表S2的值。如果你的答案和标准答案的“相对误差”小于1e-8，你的答案会被视为正确的答案。

Samples

1
ATATATA

0.750000

Limitation

1s, 1024KiB for each test case.