Breaking the Vigenère Cipher

Nick Fury has learned that Black Widow and Hawkeye are exchanging secret messages using a Vigenère cipher, and he is worried about a possible rebellion. Reading the description of the cipher, he was discouraged to find it once described as le chiffre indéchiffrable ("the indecipherable cipher"), and he now wants your help to break it.

You keep reading and discover that the cipher is actually quite insecure. In 1846 Charles Babbage decrypted a sample of ciphertext using a technique later published by Kasiski and known as Kasiski examination.

Kasiski examination guesses the length of the keyword by looking for repeated groups of letters in the ciphertext. For example, consider the following plaintext, keyword (repeated as needed), and ciphertext:

Keyword:    ABCDABCDABCDABCDABCDABCDABCD
Plaintext:  CRYPTOISSHORTFORCRYPTOGRAPHY
Ciphertext: CSASTPKVSIQUTGQUCSASTPIUAQJB

The plaintext contains the repeated substring CRYPTO, and because the two occurrences happen to align with the same part of the repeated keyword, both are encrypted to the same ciphertext CSASTP. We denote such a repeated ciphertext substring by a triple $\langle s, p, q\rangle$, where $s$ is the repeated string and $p < q$ are the 1-based starting positions of its two occurrences. The repetition above is $\langle \texttt{CSASTP}, 1, 17\rangle$, with distance $q - p = 16$. The keyword length is guessed to be a factor of this distance (here $1, 2, 4, 8,$ or $16$).

A repeated group may also be a coincidence, so the guessing algorithm must tolerate some noise.

Your task is to find the possible keyword lengths for a given ciphertext, using only repeated groups of exactly 3 letters. Find every group of length exactly 3 that occurs more than once; for each such group, every unordered pair of its occurrence positions forms one triple. Say the triples are $\langle s_1, p_1, q_1\rangle, \langle s_2, p_2, q_2\rangle, \dots, \langle s_n, p_n, q_n\rangle,$ with distances $x_i = q_i - p_i$. A number $k$ is a guess for the keyword length if and only if $k$ divides at least 90% of the distances $\{x_1, \dots, x_n\}$. We only consider key lengths with $4 \le k \le 20$. If there are no repeated triples at all (the set of distances is empty), there are no guesses.

Overlapping groups are counted separately, which naturally gives longer repeats more weight. For example, the ciphertext VHVSSPQUCEMRVBVBBBVHVSURQGIBDUGRNICJQUCERVUAXSSR has two repeated groups of length 4, which yield four repeated groups of length 3: VHV, HVS, QUC, and UCE (VHV and HVS are counted separately even though they overlap). Their distances are $18, 18, 30, 30$, and the only key length between 4 and 20 that divides at least 90% of them is $6$.

The first line contains the number of test cases $T$ ($T < 100$). Each of the following $T$ lines contains one test case: a single string, the ciphertext. The ciphertext consists only of capital letters A–Z; all digits, punctuation, and whitespace have already been stripped out.

For each test case, print the guesses for the keyword length between 4 and 20 (inclusive). If there is at least one guess, print Possible key lengths between 4 and 20: followed by a single space and the guesses in increasing order, separated by single spaces. If there are no guesses, print No guesses found. instead.