Cho dãy số: ~1, 1 × 2, 1 × 2 × 3, 1 × 2 × 3 × 4, ...~ (Số thứ ~N~ là tích của các số từ 1 đến ~N~).

Hỏi chữ số cuối cùng khác 0 của số thứ ~N~ trong dãy là chữ số nào?

Input

• Nhập vào một số tự nhiên ~N~ (~1 \leq N \leq 10^4~).

Output

• In ra chữ số cuối cùng khác 0 của số thứ ~N~ trong dãy.

Example

Input

3

Output

6

Input

6

Output

2

Giải thích

• Với ~N = 3~, ta có: ~1 × 2 × 3 = 6~ → chữ số cuối cùng là 6.
• Với ~N = 6~, ta có: ~1 × 2 × 3 × 4 × 5 × 6 = 720~ → chữ số cuối cùng khác 0 là 2.

Scoring

• 60 điểm nếu chương trình chạy đúng với ~N \leq 15~.
• 100 điểm nếu chương trình chạy đúng với ~N \leq 10^4~.

Cho ~N~ số tự nhiên ~a_1, a_2, a_3, \dots, a_n~. Hãy đếm số lượng chữ số ~0~ tận cùng có nghĩa của tích ~a_1 \times a_2 \times a_3 \times \dots \times a_n~.

Input

• Dòng đầu tiên chứa số ~N~.
• Dòng thứ hai chứa ~N~ số tự nhiên ~a_1, a_2, a_3, \dots, a_n~.

Output

• In ra số lượng số chữ số ~0~ tận cùng có nghĩa của ~N~ số đã cho.

Subtasks

• Subtask ~1~ (~50\%~ số điểm): ~N \leq 18, a_i \leq 10~.
• Subtask ~2~ (~50\%~ số điểm): ~N \leq 100, a_i \leq 10^9~.

Sample Test

Input:

5
2 5 4 9 10

Output:

2

Note:

• ~2 \times 5 \times 4 \times 9 \times 10 = 3600~ có ~2~ chữ số ~0~ tận cùng có nghĩa.

Cho số nguyên dương ~k~. Đếm số cặp ~(a, b)~ thoả mãn ~a, b~ là hai số nguyên dương và ~a^2 + b^2 \leq k~.

Lưu ý: Hai cặp ~(a, b)~ và ~(b, a)~ được coi là hai cặp khác nhau.

Input

• Gồm một số nguyên dương ~k~ duy nhất.

Output

• In ra số cặp ~(a, b)~ thoả mãn.

Subtasks

• Subtask ~1~ (~30\%~ số điểm): ~k \leq 10^3~;
• Subtask ~2~ (~20\%~ số điểm): ~10^3 < k \leq 10^6~;
• Subtask ~3~ (~50\%~ số điểm): ~10^6 < k \leq 10^{12}~.

Sample Test

Input:

8

Output:

4

Note: Các cặp thoả mãn là ~(1, 1); (1, 2); (2, 1); (2, 2)~.

Cho số nguyên dương ~N~. Đếm xem có bao nhiêu cặp số nguyên ~a, b~ (~0 < a \leq b~) sao cho tổng các số nguyên trong đoạn ~[a, b]~ bằng ~N~.
Hai đoạn khác nhau là hai đoạn có ít nhất một phần tử khác nhau.

Input

• Gồm một dòng duy nhất chứa số nguyên dương ~N~ (~0 < N < 10^{15}~).

Output

• Một số nguyên dương duy nhất là kết quả của bài toán – số lượng đoạn thỏa mãn.

Example

Input

9

Output

3

Giải thích

Có ba đoạn thỏa mãn:

• ~[2, 4]~ → 2 + 3 + 4 = 9
• ~[4, 5]~ → 4 + 5 = 9
• ~[9, 9]~ → 9 = 9

Lưu ý

• 40% số test ứng với ~N \leq 10^4~
• 30% số test ứng với ~10^4 < N \leq 10^8~

Một số tự nhiên được gọi là đặc biệt nếu số đó lớn hơn ~0~ và tổng chữ số của nó chia hết cho ~10~. Tìm số đặc biệt thứ ~N~.

Input

• Dòng đầu tiên gồm số ~T~ - số lượng test case.
• ~T~ dòng tiếp theo, mỗi dòng chứa một số ~N~.

Output

• Với mỗi test case, hãy in ra trên một dòng số đặc biệt thứ ~N~. Có thể chứng minh được rằng kết quả luôn nhỏ hơn ~2^{64}~.

Subtasks

• Subtask ~1~ (~30\%~ số điểm): ~1 \leq T \leq 10; 1 \leq N \leq 10^5~.
• Subtask ~2~ (~70\%~ số điểm): ~1 \leq T \leq 10^5; 1 \leq N \leq 10^{18}~.

Sample Test

Input:

2
1
2

Output:

19
28

Note:

• Số đặc biệt thứ ~1~ là ~19~, thứ ~2~ là ~28~.

Gọi ~f(x)~ là số lượng các số nguyên dương từ ~1~ đến ~x~ mà chia hết cho ~2~ hoặc chia hết cho ~3~ nhưng không chia hết cho ~6~. Tính tổng tất cả các ~f(i)~ vói ~i~ nằm trong khoảng từ ~l~ đến ~r~.

Input

• Gồm một dòng chứa hai số nguyên dương ~l~, ~r~. (~r - l \leq 10^6~)

Output

• In ra tổng các ~f(i)~ với ~i~ nằm trong khoảng từ ~l~ đến ~r~.

Subtasks

• Subtask ~1~ (~25\%~ số điểm): ~l \leq r \leq 10^3~.
• Subtask ~2~ (~25\%~ số điểm): ~l = 1, r \leq 10^6~.
• Subtask ~3~ (~25\%~ số điểm): ~l = r, r \leq 10^9~.
• Subtask ~4~ (~25\%~ số điểm): ~l \leq r \leq 10^9~.

Sample Test

Input:

3 8

Output:

18

Note:

• ~f(3) = 2~ (các số thoả mãn: ~2, 3~).
• ~f(4) = 3~ (các số thoả mãn: ~2, 3, 4~).
• ~f(5) = 3~ (các số thoả mãn: ~2, 3, 4~).
• ~f(6) = 3~ (các số thoả mãn: ~2, 3, 4~).
• ~f(7) = 3~ (các số thoả mãn: ~2, 3, 4~).
• ~f(8) = 4~ (các số thoả mãn: ~2, 3, 4, 8~).

Yakumo Ran rất giỏi toán, nhưng với những số rất lớn cô sẽ gặp khó khăn nên cô nhờ các bạn giúp bài toán sau.

Cho hai số nguyên dương ~a,b~, hãy tính: ~\sum_{i=a}^b~ ~⌊\sqrt{i}⌋~.

Ở đây, ~⌊a⌋~ có nghĩa là số nguyên lớn nhất không lớn hơn ~a~.

Input

• Gồm một dòng chứa hai số nguyên dương ~a,b~.

Output

• In ra kết quả của bài toán.

Sample Test

Input 1

3 10

Output 1

17

Giải thích

~⌊\sqrt{3}⌋+⌊\sqrt{4}⌋+⌊\sqrt{5}⌋+⌊\sqrt{6}⌋+⌊\sqrt{7}⌋+⌊\sqrt{8}⌋+⌊\sqrt{9}⌋+⌊\sqrt{10}⌋~ ~=1+2+2+2+2+2+3+3=17~

Input 2

14 29

Output 2

67

Giới hạn:

• Subtask 1 (60% số điểm): ~a,b \le 10^6~
• Subtask 2 (40% số điểm): ~a,b \le 10^{12}~