定义 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。