Bé Bo đang học về tính lẻ chẵn. Hôm nay, cô giáo dạy Toán cho Bo bài toán như sau: Cho hai số nguyên dương ~x~, ~y~. Dãy số A được xây dựng theo quy tắc:

• ~A_1 = x~
• ~A_2 = y~
• ~A_i = (A_{i - 1} + A_{i-2}) % k~ nếu i ≥ 3 và i chỉ số chẵn
• ~A_i = |A{i-1} - A{i-2}|%k~ nếu ~i ≥ 3~ và ~i~ là chỉ số lẻ Trong đó ~k=10^9+7~ và ~%~ là phép chia lấy phần dư, ~|A_{i-1}-A_{i-2}|~ là giá trị tuyệt đối của ~A_{i-1} - A_{i-2}~

Ví dụ: với ~x = 5~, ~y=7~ thì một vài phần tử đầu tiên của dãy số ~A~ là: ~5, 7, 2, 9, 7, 16, 9, 25, 16, 41…~

Yêu cầu: Cho trước số nguyên dương n, hãy tính An.

Input

• Gồm một dòng chứa ba số nguyên dương lần lượt là ~x~,~y~,~n~, giữa các số cách nhau bởi một dấu cách. (~1 ≤ x, y ≤ 10^9, 3 ≤ n ≤ 10^6~)

Output

• Một số nguyên là giá trị của An.

Example

Input

5 7 8

Output

25

Bo là cậu bé thích đọc sách. Tuy chưa được học đến chuyên đề "Số học" nhưng Bo muốn nghiên cứu trước về nó. Bo đã đến thư viện tìm kiếm cuốn sách có bài toán liên quan đến nội dung này để thử sức mình. Bài toán Bo tìm thấy có yêu cầu như sau: "Cho một số nguyên dương ~n~(~n ≤ 5 * 10^{17}~). Tìm chữ số lớn thứ ~k~ trong ~n~.

? Theo em, Bo làm thế nào để tìm ra đáp án đúng?

Input

• Dòng đầu tiên chứa số ~n~.
• Dòng thứ hai chứa số ~k~(~0 < k ≤ 9~).

Output

• Ghi một số là chữ số lớn thứ ~k~ trong ~n~.

Scoring

• Có 50% test tương ứng 50% số điểm của bài với ~n ≤ 10^6~.
• Có 40% test tương ứng 40% số điểm của bài với ~n ≤ 10^9~.
• Có 10% test tương ứng 10% số điểm của bài với ~n ≤ 5 * 10^{17}~.

Examples

Input

7853
3

Output

5

Input

509890
2

Output

8

Số "siêu nguyên tố" được định nghĩa như sau: Là một số nguyên tố và tổng các chữ số của nó là một số nguyên tố. Ví dụ: Số ~131~ là số siêu nguyên tố vì ~131~ là một số nguyên tố và tổng các chữ số của nó là: ~1 + 3 + 1 = 5~ là một số nguyên tố.

Yêu cầu: Cho dãy gồm ~N~ số nguyên dương ~a_1, a_2,..., a_N~. Hãy lập trình in ra số lượng các số siêu nguyên tố trong dãy. Nếu trong dãy không có số nào là số siêu nguyên tố thì in ra ~0~.

Input

• Dòng đầu tiên là số nguyên duong ~N~ (~1 ≤ N ≤ 10^6~).

• Dòng tiếp theo ghi ~N~ số ~a_1, a_2,..., a_N~ (~1 ≤ a_i ≤ 10^6, với 1 ≤ i ≤ N~).

Output

• Một số duy nhất là số lượng số siêu nguyên tố có trong dãy.

Scoring

Có 40% số điểm ứng với các test có ~N ≤ 10^3; a_i ≤ 10^3~.

Có 30% số điểm ứng với các test có ~N ≤ 10^4; a_i ≤ 10^6~.

Có 30% số điểm ứng với các test có ~N ≤ 10^6; a_i ≤ 10^6~.

Examples

Input

5
31 12 131 22 151

Output

2

Input

5
17 9 18 15 16

Output

0

Note

• Ở ví dụ 1, có 2 số siêu nguyên tố là ~131~ và ~151~.

• Ở ví dụ 2, không có số siêu nguyên tố nào.

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.