Генератор Случайных Чисел по фон-Нейманну

Случайные числа часто нужны при программировании игр или в научных исследованиях. Не менее нужны они и в обычных бизнес-приложениях (вспомните генерацию уникальных ключей, паролей). Как устроены генераторы случайных чисел? Вот один из старинных и несложных алгоритмов - хотя он носит имя фон-Нейманна, по-видимому он был известен много веков назад.

1. Возьмём некое исходное четырехзначное число (т.е. в диапазоне 0000 ... 9999).
2. Возведем его в квадрат (т.е. умножим на себя же) и получим число с 8 знаками (добавим ведущие нули при необходимости).
3. Обрежем два первых и два последних знака в десятичном представлении результата.
4. Новое значение опять содержит 4 цифры и мы используем его как следующее число в последовательности.
5. Чтобы получить дальнейшие значения - повторяем с пункта 2.

Пример:

5761                      - вот исходное число
5761 * 5761 = 33189121    - возвели в квадрат
33(1891)21 => 1891        - вырезали 4 цифры из середины

1891                      - итак, это второе число последовательности
1891 * 1891 = 3575881     - возведем в квадрат (нужно приписать ведущий ноль чтоб стало 8 цифр)
03(5758)81 => 5758        - вырезаем 4 знака из середины

5758                      - итак, это третье число последовательности (и так далее...)

Очевидно, раньше или позже любая последовательность замкнётся в каком-нибудь цикле, например:

0001 -> 0000 -> 0000                   - повторение (0000) после 2 итераций
4100 -> 8100 -> 6100 -> 2100 -> 4100   - повторение (4100) после 4 итераций

Нам будут даны начальные значения для нескольких последовательностей. Требуется ответить за какое число итераций каждая последовательность придёт к повторению.

Входные данные содержат количество тестов в первой строке.
Вторая строка содержит сами тесты - начальные значения последовательностей, через пробел.
Ответ должен содержать количество итераций до повторения для каждой последовательности.

Пример:

входные данные:
3
0001 4100 5761

ответ:
2 4 88

Подсказка: Чтобы обрезать 8-значное число, поделите на 100 а потом возьмите остаток от деления на 10000.