Niektóre liczby naturalne w notacji dziesiętnej składają się wyłącznie z zer i jedynek, zawierając przynajmniej jedną jedynkę. Przykładowymi liczbami spełniającymi te założenia są 10, 101, 1111, 11010. Jeżeli liczba nie spełnia powyższych założeń, tzn. zawiera cyfry inne niż 0 i 1, można próbować pomnożyć ją przez dodatnią liczbę całkowitą, tak aby w wyniku uzyskać liczbę złożoną wyłącznie z zer i jedynek. Przykładowo mając liczbę 19, można pomnożyć ją przez 579 w wyniku otrzymując 11001. Liczba 579 jest zarazem minimalną liczbą naturalną przez którą należy pomnożyć 19 aby uzyskać liczbę złożona wyłącznie z zer i jedynek.
Twoim zadaniem jest napisanie programu, który dla danej liczby naturalnej N (1 ≤ N ≤ 1 000 000) wyznaczy minimalną liczbę przez którą należy pomnożyć N aby uzyskać w wyniku liczbę złożoną wyłącznie z zer i jedynek.
Dane wejściowe składają się z K zestawów danych. W pierwszym wierszu wejścia znajduje się liczba zestawów danych.
Każdy zestaw danych składa się z jednego wiersza zawierającego liczbę naturalną N (1 ≤ N ≤ 1 000 000) dla której należy wyznaczyć liczbę złożoną wyłącznie z zer i jedynek.
Dane wyjściowe składają się z K wierszy. Jeden wiersz odpowiada jednemu zestawowi danych wejściowych i zawiera liczbę cyfr liczby złożonej wyłącznie z zer i jedynek, uzyskanej przez pomnożenie N przez minimalną liczbę całkowitą.
6 478523 18 97623 111 2762 8
21 10 17 3 11 4