Хранение ключей

Карл разрабатывает сервис хранения ключей. У каждого пользователя есть положительный целочисленный ключ.

Карл знает, что хранить ключи в виде обычного текста - плохая практика. Поэтому вместо хранения ключа он решил сохранить отпечаток ключа. Однако использование какого-то существующего алгоритма отпечатков пальцев показалось ему слишком скучным, поэтому он изобрел свой собственный.

Отпечаток Карла вычисляется с помощью следующего процесса: разделите данное целое число на 2, затем разделите результат на 3, затем разделите результат на 4 и так далее, пока мы не получим результат, равный нулю (мы каждый раз говорим о целочисленном делении). Отпечаток пальца определяется как мультимножество остатков этих делений.

Например, вот как алгоритм отпечатка пальца Карла применяется к ключу 11: 11 деленное на 2, имеет остаток 1 и результат 5, затем 5 деленное на 3 имеет остаток 2 и результат 1, а 1 деленное на 4 имеет остаток 1 и результат 0. Таким образом, ключ 11 создает последовательность остатков [1, 2, 1] и имеет мультимножество отпечатков {1, 1 , 2}.

Ксения хочет доказать, что алгоритм отпечатка пальца Карла не очень хорош. Например, она обнаружила, чтооба ключа 178800 и 123456 создают отпечаток {0, 0, 0, 0, 2, 3, 3, 4}. Таким образом, пользователи подвергаются риску столкновения отпечатков пальцев с некоторыми часто используемыми и легко угадываемыми ключами, такими как 123456.

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

Входные данные

Первая строка содержит целое число t (1 ≤ t ≤ 50000) - количество часто используемых ключей для проверки. Каждая из следующих t строк содержит одно целое число k[i] (1 ≤ k[i] ≤ 10^18) - сам ключ.

Выходные данные

Для каждого ключа выведите одно целое число - количество других ключей с таким же отпечатком пальца.

Примеры

Примечание

Другой ключ с тем же отпечатком пальца, что и 11, является 15. 15 производит последовательность остатков [1, 1, 2]. Таким образом, оба числа имеют мультимножество отпечатков пальцев {1, 1, 2}.