AlgoLiga 2018

Mały Jasio siedząc w domu w to szare jesienne popołudnie postanowił poeksperymentować z matematyką. Zaczął pracowicie wypisywać liczby oraz ich wielokrotności. Po pewnym czasie zauważył, że dla wielu z tych liczb istnienią wielokrotności składające się z samych jedynek. Na przykład dla liczby 3 najmniejszą taką wielokrotnością jest 111. Pytanie jak będzie dla innych liczb? Jest pewien, że uda mu się znaleźć tutaj jakiś schemat, jednak potrzebuje więcej danych. Niestety nie umie programować i musisz mu w tym pomóc.

Wejście

Wejście rozpoczyna liczba testów 10 < t ≤ 10⁴. Pojedynczy test składa się z jednej liczby 0 ≤ n ≤ 10⁹. Można założyć, że n*t ≤ 10⁹.

Wyjście

Dla każdego testu należy wypisać odpowiedź w oddzielnej linii. Odpowiedzią jest ilość cyfr w zapisie dziesiętnym najmniejszej wielokrotności liczby n składającej się tylko z cyfry 1. Jeśli taka nie istnieje to należy wypisać jedno słowo "NIE" (bez cudzysłowu).

Przykład

Wejście:
3
3
7
9901

Wyjście:
3
6
12