Cho ~3~ số nguyên tố ~a~, ~b~, ~c~ và số nguyên dương ~n~, hãy đếm xem trong khoảng từ ~1~ tới ~n~, có bao nhiêu số chia hết cho ít nhất một trong ~3~ số ~a,b,c~.

Input

• Gồm một dòng chứa ~4~ số ~a,b,c,n~, trong đó ~a,b,c~ là số nguyên tố và đôi một khác nhau, ~n~ là một số nguyên dương.

Output

• In ra số số nguyên dương trong khoảng ~[1,n]~ chia hết cho ít nhất một trong ~3~ số ~a,b,c~.

Điều kiện

• ~1 \le a,b,c \le 10^6~.
• ~1 \le n \le 10^{18}~.

Subtask

• ~50\%~ số điểm: ~n \le 10^6~.
• ~50\%~ số điểm: Không ràng buộc gì thêm.

Ví dụ

Input 1:

2 3 5 9

Output 1:

7

Input 2:

3 5 7 20

Output 2:

11

Cho hai số nguyên dương ~l, r~. Hãy tính giá trị của ~\displaystyle\sum_{i=l}^rS(i)~, biết rằng ~S(n)~ được định nghĩa là tổng các số nguyên dương từ ~1~ đến ~n~.

Input

Một dòng duy nhất gồm hai số nguyên ~l, r \ (1 \le l \le r \le 10^{12}).~

Output

In ra kết quả cần tìm sau khi chia lấy dư cho ~10^9 + 7~.

Scoring

• Subtask 1 [25%]: ~l \le r \le 500;~
• Subtask 2 [25%]: ~r - l \le 10^6;~
• Subtask 3 [25%]: ~l = 1;~
• Subtask 4 [25%]: Không có ràng buộc gì thêm.

Examples

Input

3 5

Output

31

Giải thích

~S(3) + S(4) + S(5) = (1 + 2 + 3) + (1 + 2 + 3 + 4) + (1 + 2 + 3 + 4 + 5) = 31.~

Viết liền các số nguyên dương liên tiếp, từ nhỏ đến lớn, bắt đầu từ ~1~, ta sẽ được một dãy dài vô hạn gồm các chữ số: ~123456789101112131415161718192021222324252627282930313233343536\ldots~

Bạn được cho số nguyên dương ~k~, nhiệm vụ của bạn là tìm chữ số thứ ~k~ của dãy trên.

Input

• Dòng thứ nhất chứa số nguyên dương ~T~ - số bộ dữ liệu. (~T \leq 10^3~)
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~k~.

Output

• In ra ~T~ dòng, mỗi dòng chứa một chữ số cho bộ dữ liệu tương ứng.

Subtasks

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

Sample Test

Input

5
8
18
16
14
19

Output

8
1
1
1
4

An làm việc ở một công ty tư vấn đầu tư chứng khoán. Nhiệm vụ của An là phân tích sự dao động chỉ số chứng khoán hàng ngày của sàn giao dịch, từ đó có thể đưa ra các thông tin hữu ích để tư vấn cho các nhà đầu tư. An nhận được dãy số nguyên dương ~A~ trong đó ~A_i~ là chỉ số chứng khoán của ngày thứ ~i~ và phải tìm một số ngày liên tiếp dài nhất sao cho chênh lệch chỉ số chứng khoán giữa hai ngày bất kỳ trong đó không vượt quá ~d~.

Ví dụ, với dãy chỉ số chứng khoán trong 6 ngày liên tiếp lần lượt là: ~10, 12, 34, 40, 30, 41~ và ~d = 10~ thì dãy chỉ số chứng khoán liên tiếp ~10, 12~ có chênh lệch chỉ số chứng khoán giữa hai ngày bất kỳ trong dãy không quá 10, nhưng dãy chỉ số chứng khoán liên tiếp ~34, 40, 30~ mới là dãy liên tiếp dài nhất.

Yêu cầu: Cho ~d~ và dãy các chỉ số chứng khoán ~A~. Hãy đưa ra số lượng ngày liên tiếp dài nhất sao cho chênh lệch chỉ số chứng khoán giữa hai ngày bất kỳ trong đó không vượt quá ~d~.

INPUT

Dòng đầu tiên chứa hai số nguyên ~n~ và ~d~ (~1 \le n \le 10^5~, ~0 \le d \le 100~).

Dòng thứ hai chứa ~n~ số nguyên dương là các chỉ số chứng khoán của lần lượt các ngày từ ~1~ đến ~n~.

OUTPUT

Gồm một số nguyên là số lượng ngày liên tiếp dài nhất thỏa mãn các điều kiện đã nêu, nếu không tồn tại hai ngày liên tiếp mà chênh lệch chỉ số chứng khoán không vượt quá ~d~ thì ghi số ~1~.

SAMPLE INPUT 1

6 10
10 12 34 40 30 41

SAMPLE OUTPUT 1

3

Giải thích: Dãy ~34, 40, 30~ độ dài ~3~ là dãy dài nhất thỏa mãn chênh lệch các phần tử không quá ~10~

SAMPLE INPUT 2

5 9
10 20 30 20 9

SAMPLE OUTPUT 2

1

Giải thích: Không có dãy con liên tiếp nào có độ dài lớn hơn 1 có chênh lệch không vượt quá 9.

SCORING

60% số test ứng với 60% số điểm của bài toán có ~n \le 1000~