Source: Super League of Chinese College Students Algorithm Design 2022, Contest 2 by HDU.

Problem Description

Kayzin plans to buy a luxury cruise ship which will cost N coins. But Kayzin didn't have enough coins, so Kayzin decided to start saving coins.

Kayzin will put $7$ or $31$ or $365$ coins into his piggy bank each day. Now Kayzin wants to know at least how many days he will need to "exactly"(No more and no less) scrape together the money for buying a luxury cruise.

If Kayzin can't "exactly" scrape together the money for buying a luxury cruise, print $-1$.

Input

The first line contains an integer $T(T\le 1000)$ . Then $T$ test cases follow.

For one case, the first line contains an integer $N$ $(1\le N\le 10^{18})$ , $N$ denotes the coins that a luxury cruise ship will cost.

Output

Print an integer for each case, indicating the minimum number of days Kayzin needs.

If Kayzin can't "exactly" scrape together the money for buying a luxury cruise, print $-1$.

Sample

5
14
38
55
403
996

2
2
-1
3
16