Trong buổi thi môn chuyên Tin học, sau khi trải qua hai bài đầu tiên của đề thi khá nhẹ nhàng, Tuyển bắt đầu gặp thử thách ở bài thứ 3. Ở bài này, Tuyển được giới thiệu về "Số tiến đẹp": là số nguyên dương có từ 2 chữ số trở lên, "tiến" nếu các chữ số từ trái sang phải tăng dần và "đẹp" nếu tổng các chữ số chia hết cho 9.

Yêu cầu: Cho số nguyên dương ~n~. Tuyển phải viết chương trình để cho biết số đó có phải là số tiến đẹp hay không?

Input

• Gồm 1 số nguyên dương n duy nhất (~1 ≤ n ≤ 10^9~).

Output

• In ra giá trị ~n~ nếu ~n~ là số tiến đẹp, ngược lại ỉn ra  - 1.

Examples

Input

235

Output

-1

Input

1224

Output

-1

Input

12357

Output

12357

Yêu cầu: Cho ~Q~ câu hỏi, mỗi câu hỏi dạng sau: Hãy đếm các số là bội của 3 hoặc 7 trong phạm vi không vượt quá ~N~ (~N~ là số nguyên dương).

Input Dòng đầu là số tự nhiên ~Q~ là số câu hỏi (~1 ≤ Q ≤ 100~).

Q dòng sau, mỗi dòng ghi một số nguyên dương ~N~ (~3 ≤ N ≤ 10^{12}~).

Output

• In ra số các bội của 3 hoặc 7 tương ứng với từng câu hỏi, được ghi trên từng dòng.

Scoring

• Có 50% số điểm ứng với các test có ~Q ≤ 100, 3 ≤ N ≤ 10^6~.

Có 50% số điểm ứng với các test có ~Q ≤ 100, 10^7 < N ≤ 10^{12}~.

Example

Input

2
6
14

Output

2
6

Note

Trong phạm vi ~[1, 6]~ có 2 số là bội của 3 hoặc 7, là 3 và 6.

Trong phạm vi ~[1, 14]~ có 6 số là bội của 3 hoặc 7, là 3, 6, 7, 9, 12, 14.

Lam là học sinh có thành tích cao trong kỳ thi tuyển sinh vào lớp 10 chuyên Tin. Phần thưởng cho em là một phần mềm diệt virus. Mã số của phần mềm là một dãy gồm n số nguyên dương ~A_1, A_2, A_3, …A_n~ . Để cài đặt được phần mềm, Lam phải nhập vào mật khẩu của phần mềm. Mật khẩu là số lượng các số chia hết cho 90 của dãy số trên.

Yêu cầu: Hãy tìm mật khẩu để cài đặt phần mềm

Input

• Dòng 1: Ghi 1 số nguyên dương ~n~ (~1 ≤ n ≤ 10^3~).

• N dòng sau, dòng thứ i ghi số nguyên ~A_i~ (~1 ≤ A_i ≤ 10^{1000}~).

Output

• Duy nhất một số là mật khẩu tìm được

Examples

Input

4
90
10
90
27052023

Output

2

Input

1
9

Output

0

Yêu cầu:

Cho 1 dãy số nguyên gồm ~n~ số cho trước. Hãy đếm tất cả các số chính phương, nguyên tố, hoàn hảo, phong phú trong dãy.

Giải thích:

• Ước thực sự của 1 số là tập hợp tất cả các ước dương nhỏ hơn nó.
• Số chính phương là số có căn bậc 2 của nó là một số nguyên.
• Số nguyên tố là số chỉ có 2 ước là 1 và chính nó.
• Số hoàn hảo là số có tổng các ước thực sự của nó bằng chính nó. Ví dụ, số 6 có tổng các ước số (không kể 6) là 1 + 2 + 3 = 6. Do đó 6 là một số hoàn hảo.
• Số phong phú là số có tổng các ước thực sự của số đó lớn hơn số đó. Ví dụ, số 12 có tổng các ước số (không kể 12) là 1 + 2 + 3 + 4 + 6 = 16 > 12. Do đó 12 là một số phong phú.

Input:

• Dòng 1: Ghi số nguyên 𝑛 ~(1 \le n \le 10^6)~
• Dòng 2: Ghi 𝑛 số nguyên ~A_1, A_2,...,A_n, 1 \le A_i \le 10^6~

Output:

• Dòng 1: Ghi 4 số nguyên dương lần lượt là số lượng các số chính phương, nguyên tố, hoàn hảo, phong phú tìm được trong dãy.

Example:

Input:

7
2 3 5 7 12 8 6

Output:

0 4 1 1

Có ~𝑁~ sợi dây loại ~𝑨~ có độ dài lần lượt là ~𝑎_1 ,𝑎_2 ,…,𝑎_N~ ; ~𝑁~ sợi dây loại ~𝑩~ có độ dài lần lượt là ~𝑏_1 ,𝑏_2 ,…,𝑏_N~ ; ~𝑁~ sợi dây loại ~𝑪~ có độ dài lần lượt là ~𝑐_1 ,𝑐_2 ,…,𝑐_N~ ; ~𝑁~ sợi dây loại ~𝑫~ có độ dài lần lượt là ~𝑑_1 ,𝑑_2 ,…,𝑑_N~ .

Yêu cầu: Hãy đếm số cách chọn đúng 1 sợi dây loại ~𝑨~, 1 sợi dây loại ~𝑩~, 1 sợi dây loại 𝑪 và 1 sợi dây loại ~𝑫~ sao cho tổng độ dài bằng ~𝐿~.

Dữ liệu vào:

• Dòng 1: Ghi hai số nguyên dương ~𝑁~ và ~𝐿~ (~1 ≤ 𝑁 ≤ 1000~;~1 ≤ 𝐿 ≤ 10^9~).
• Dòng 2: Ghi ~𝑁~ số nguyên dương ~𝑎_1 ,𝑎_2 ,…,𝑎_N~ (~1 ≤ 𝑎_i≤ 10^9 ;1 ≤ 𝑖 ≤ 𝑁~) lần lượt là độ dài của ~𝑁~ sợi dây loại ~𝑨~.
• Dòng 3: Ghi ~𝑁~ số nguyên dương ~𝑏_1 ,𝑏_2 ,…,𝑏_N~ (~1 ≤ 𝑏_i ≤ 10^9 ;1 ≤ 𝑖 ≤ 𝑁~) lần lượt là độ dài của ~𝑁~ sợi dây loại ~𝑩~.
• Dòng 4: Ghi ~𝑁~ số nguyên dương ~𝑐_1 ,𝑐_2 ,…,𝑐_N~ (~1 ≤ 𝑐_i ≤ 10^9 ;1 ≤ 𝑖 ≤ 𝑁~) lần lượt là độ dài của ~𝑁~ sợi dây loại ~𝑪~.
• Dòng 5: Ghi ~𝑁~ số nguyên dương ~𝑑_1 ,𝑑_2 ,…,𝑑_N~ (~1 ≤ 𝑑_i≤ 10^9 ;1 ≤ 𝑖 ≤ 𝑁~) lần lượt là độ dài của ~𝑁~ sợi dây loại ~𝑫~.

Dữ liệu ra:

• Dòng 1: Ghi một số nguyên ~𝑇~ là kết quả tìm được.

Ví dụ:

Input

3 28 
1 1 1 
1 1 1 
10 11 12 
13 14 15 

Output

18