Зберігання ключів

Карл розробляє сервіс для зберігання ключів. У кожного користувача є додатний цілий числовий ключ.

Карл розуміє, що зберігати ключі у вигляді звичайного тексту — це погана практика. Тому замість зберігання самого ключа він вирішив зберігати його відбиток. Проте використання існуючих алгоритмів для створення відбитків здалося йому занадто банальним, тому він придумав власний метод.

Відбиток Карла обчислюється наступним чином: розділіть дане ціле число на 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}.