Hai số nguyên tố cùng nhau là hai số có ước chung lớn nhất bằng 1.

Yêu cầu: Cho số nguyên dương ~n~. Tìm số lượng các số nguyên dương ~x~ nhỏ hơn ~n~ thỏa mãn: ~x~ và ~n~ là hai số nguyên tố cùng nhau.

INPUT

Một dòng duy nhất chứa số nguyên dương ~n~ (~2 \le n \le 2\times 10^{6}~).

OUTPUT

Một dòng duy nhất chứa một số nguyên — số lượng các số nguyên dương ~x~ (nhỏ hơn ~n~) và nguyên tố cùng nhau với ~n~.

SAMPLE INPUT 1

4

SAMPLE OUTPUT 1

2

SAMPLE INPUT 2

15

SAMPLE OUTPUT 2

8

GIẢI THÍCH

• Với ~n=4~: các số ~1,2,3~ nhỏ hơn ~4~ thì chỉ có ~1~ và ~3~ là coprime với ~4~ nên đáp án là ~2~.
• Với ~n=15~: trong ~1..14~ có ~1,2,4,7,8,11,13,14~ là coprime với ~15~ nên đáp án là ~8~.

SUBTASKS

An và Khoa rất yêu thích học lập trình. Trong giờ ra chơi, An ghi lên bảng hai chuỗi ký tự ~A~ và ~B~ (chứa các chữ cái tiếng Anh). Chuỗi ~A~ có độ dài nhỏ hơn ~10^2~, chuỗi ~B~ có độ dài nhỏ hơn ~10^4~. An nhờ Khoa đếm số lần xuất hiện của một hoán vị của chuỗi ~A~ trong chuỗi ~B~.

Yêu cầu: Hãy giúp Khoa giải bài toán trên.

INPUT

Hai dòng:

• Dòng 1: chuỗi ký tự ~A~.
• Dòng 2: chuỗi ký tự ~B~.

Cả hai chuỗi chỉ gồm chữ cái Latinh. ~|A| \le 10^2,\; |B| \le 10^4~.

OUTPUT

Một số nguyên duy nhất — số lần xuất hiện của một hoán vị của ~A~ trong ~B~.

SAMPLE INPUT 1

d
ggdneh

SAMPLE OUTPUT 1

1

Giải thích: Hoán vị chuỗi ~A~ (chỉ có ký tự 'd') xuất hiện tại vị trí thứ 3 của chuỗi ~B~.

SAMPLE INPUT 2

bbb
abbcbbbabbbbhgbbb

SAMPLE OUTPUT 2

4

Giải thích: Có 4 đoạn con của ~B~ có chiều dài 3 là hoán vị của "bbb".

SAMPLE INPUT 3

Acad
bcrdAcahgaAcd

SAMPLE OUTPUT 3

2

Giải thích: Có 2 vị trí trong ~B~ mà đoạn con độ dài ~|A|~ là hoán vị của "Acad".

SUBTASKS

An và Khoa rất thích chơi với dãy số. Hôm nay, Khoa đã nêu bài toán như sau:

Cho dãy ~A~ gồm ~n~ số nguyên ~a_1,a_2,\dots,a_n~. Ban đầu, ~a_i~ được gán bằng ~i~ ~(1 \le i \le n \le 10^{18})~. Để bài toán thú vị hơn, Khoa biến đổi các phần tử của dãy ~A~ như sau: liên tục thay thế một phần tử bằng tổng các chữ số của nó cho đến khi chỉ gồm một chữ số duy nhất.

Ví dụ: với ~i = 197~, ban đầu ~a_{197} = 197~. Khoa lần lượt biến đổi giá trị của ~a_{197}~ như sau: ~197 = 1 + 9 + 7 = 17~, tiếp tục biến đổi ~17 = 1 + 7 = 8~. Khi đó ~a_{197} = 8~.

Khoa có ~q~ câu hỏi có dạng như sau: Tổng các số từ phần tử thứ ~l~ đến phần tử thứ ~r~ của dãy ~A~ sau biến đổi là bao nhiêu?

INPUT

Dòng 1 chứa số nguyên dương ~q~ ~(1 \le q \le 100)~. ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~l, r~ ~(1 \le l \le r \le 10^{18})~.

OUTPUT

In ra ~q~ dòng, mỗi dòng chứa một số nguyên — đáp án cho mỗi truy vấn tương ứng: tổng các giá trị của ~a_l, a_{l+1}, \dots, a_r~ sau khi đã biến đổi.

SAMPLE INPUT

2
9 13
44 45

SAMPLE OUTPUT

19
17

GIẢI THÍCH

• Với truy vấn 1: các giá trị sau biến đổi của ~a_9,a_{10},a_{11},a_{12},a_{13}~ lần lượt là ~9,1,2,3,4~. Tổng = 19.
• Với truy vấn 2: ~a_{44}=8, a_{45}=9~. Tổng = 17.

SUBTASKS