定义 $580$ 数是满足数位依次为 $5,8,0$ 循环的数，例如 $580,580580580$ 是 $580$ 数，而 $508,58,5805800$ 都不是 $580$ 数。并且定义数位长为 $3n$ 的 $580$ 数是第 $n$ 个 $580$ 数，例如第 $4$ 个 $580$ 数为 $580580580580$。

给定整数 $k$，问最小的能被 $k$ 整除的 $580$ 数是第几个 $580$ 数。

输入一行一个整数 $t(1\le t\le 100)$，代表询问的个数。

接下来输入 $t$ 行，每行一个整数 $k(1\le k\le 10^9)$。

对每个询问，输出一行一个整数，代表能被整除的最小 $580$ 数的序号。如果所有 $580$ 数都无法被 $k$ 整数，输出 -1。

$580\bmod 2=0$，所以第一个 $580$ 数就满足被 $k=2$ 整除。

$580580580580580580580580580580580580580580580580\bmod 17=0$，为第 $16$ 个 $580$ 数，且计算可知，前 $15$ 个 $580$ 数均无法被 $17$ 整除。

可以证明，所有 $580$ 数模 $8$ 的结果都是 $4$。