Nếu số tự nhiên ~x~ chia hết cho số tự nhiên ~y~ thì ~x~ được gọi là bội số của ~y~.

Yêu cầu: Cho dãy ~A~ gồm ~N~ số nguyên có giá trị lần lượt là ~A_1, A_2, …, A_N (1\leq i\leq N)~. Hãy đếm số lượng các số là bội của ~3~ hoặc ~5~ trong phạm vi không quá ~A_i~.

Input

Vào từ file văn bản BOI.INP có cấu trúc như sau:

• Dòng thứ nhất chứa số nguyên ~N (1 \leq N \leq 100)~;

• Dòng thứ hai là dãy số nguyên ~A_1, A_2, …, A_N~. Các số cách nhau một dấu cách.

Output

Ghi ra file văn bản BOI.OUT mỗi kết quả ghi trên một dòng, là số lượng các bội số đã đếm được của mỗi ~A_i (1 \leq i \leq N)~.

Scoring

• Subtask ~1~ (~70\%~): số điểm tương ứng với ~1\leq A_i\leq 10^7~.

• Subtask ~2~ (~30\%~): số điểm tương ứng với ~1\leq A_i\leq 10^{12}~.

Example input 1

3
3 6 12

Example output 1

1
3
6

Note 1

• ~3~: có bội là ~3~.
• ~6~: có các bội là ~3, 5, 6~.
• ~12~: có các bội là ~3, 5, 6, 9, 10, 12~.