Cho số nguyên N. Nhiệm vụ của bạn là tìm cách biểu diễn số nguyên N bằng tổng các số nguyên tố chỉ có 1 chữ số sao cho cách biễu diễn sử dụng ít số nguyên tố nhất có thể.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên T là số bộ test
• T dòng tiếp theo mỗi dòng chứa số nguyên Ni

Dữ liệu ra:

Với mỗi giá trị ~N_i~, Ghi ra số lượng số nguyên tố ít nhất được sử dụng để biễu diễn ~N_i~. trường hợp không thể biễu diễn số nguyên Ni chỉ bằng tổng các số nguyên tố thì in ra '-1'.

RÀNG BUỘC: ~1<=T<=100; 1<=X<=10^6~

VÍ DỤ:

Input

4
7 
10
14
11

Output

1
2
2
3

Giải thích:

7 sẽ được biễu diễn bằng chính nó

10 sẽ được biễu diễn bằng 2 số : 7+3

14 sẽ được biễu diễn bằng 2 số : 7+7

11 sẽ được biễu diễn bằng 3 số : 5+3+3 hoặc 7+2+2