Description

兔子饿了，想吃萝卜。于是他来到一个环形场地，这里有3000000021 个仓库，围成一圈，分别编号为 0, 1, 2, … ,3000000020 ，每两个相邻的仓库距离 1 个单位长度。然而，由于各种自然灾害，这几年的收成都不好，仓库也几乎都空了，只有 0 号仓库，1000000007 号仓库，2000000014 号仓库还有萝卜。于是，我们可怜的小兔子沿着环形的正向，跳啊跳，跳啊跳，希望能跳到这些仓库，吃到萝卜。已知，对于任意时刻，若兔子在 x 号仓库，那么下一时刻，他可以前进 x 3 + 3 个单位长度，也可以选择前进 x 15 + 15 个单位长度，也就是，前面距离的 5 倍。那么，请问，对于给定的初始位置 x ，兔子至少跳多少次可以吃到萝卜？如果兔子跳了 100000 次，还未吃到萝卜，那么输出 -1 。

Input

一个正整数 T(1 <= T <= 60) ，表示有 T 组数据。 每组数据为一个整数 x ，表示兔子的起始位置。

Output

对于每个数据，输出一个答案，占一行。

Sample

Input

2
250000001
2000000015

Output

1
-1

Source: YCC