Trên dãy núi có ~n~ trạm dừng chân. Đoàn thám hiểm xuất phát từ trạm 1 và muốn vượt qua tất cả ~n~ trạm lần lượt từ 1 đến ~n~. Trạm thứ ~i~ có độ cao ~h_i~. Do địa hình hiểm trở và nhiệt độ thấp nên nếu chênh lệch độ cao giữa 2 trạm liên tiếp vượt qua ~D~ thì đoàn bắt buộc phải sử dụng thiết bị hỗ trợ để di chuyển. Để tiết kiệm năng lượng cho chuyến đi nên đoàn thám hiểm hạn chế sử dụng thiết bị hỗ trợ.

Yêu cầu: Tìm số lần tối thiểu phải sử dụng thiết bị hỗ trợ để di chuyển lần lượt từ trạm 1 đến trạm ~n~.

Input

• Dòng 1: chứa 2 số nguyên ~n~ và ~D~ (~n \le 10^5; D \le 10^9~).
• Dòng 2: chứa ~n~ số nguyên ~h_1, h_2, ..., h_n~ (~1 \le h_i \le 10^9~).

Output

Một số nguyên là số lần phải sử dụng thiết bị hỗ trợ.

Sample Input 1

5 10
10 25 30 45 50

Sample Output 1

2

Sample Input 2

3 100
10 20 30

Sample Output 2

0

Sample Input 3

1 5
10

Sample Output 3

0

Số nguyên dương ~X~ được gọi là "Nguyên tố cặp" nếu:

1. ~X~ là một số nguyên tố.
2. Tồn tại ít nhất một vị trí chia ~X~ thành 2 phần khác rỗng, mỗi phần đều tạo thành một số nguyên tố.

Ví dụ:

• 317 là nguyên tố cặp vì có thể chia thành 3 và 17, hoặc 31 và 7.
• 307 là nguyên tố cặp vì có thể chia thành 3 và 07 tương đương 3 và 7.
• 29 không phải nguyên tố cặp vì chia thành 2 và 9 (9 không phải số nguyên tố).
• 103 không phải nguyên tố cặp vì (1, 3) và (10, 3) đều không phải cặp nguyên tố.

Yêu cầu: Cho hai số nguyên dương ~L, R~. Hãy đếm số lượng số nguyên tố cặp trong đoạn ~[L, R]~.

Input

Dòng đầu chứa số nguyên ~T~ (~1 \le T \le 10^5~) là số lượng test.

Mỗi dòng trong ~T~ dòng tiếp theo chứa 2 số ~L, R~ (~1 \le L \le R \le 10^7~).

Output

Gồm ~T~ dòng, mỗi dòng ghi kết quả của bộ test tương ứng được cho trong dữ liệu vào.

Sample Input 1

3
10 60
310 320
1 10

Sample Output 1

3
3
0

• Test 1: Có 3 số là 23, 37, 53.
• Test 2: Có 3 số là 311, 313, 317.

Subtasks

• 25% số test: ~T \le 100; 1 \le L \le R \le 1000~.
• 25% số test: ~T \le 100; 1 \le L \le R \le 10^6~.
• 50% số test: không ràng buộc gì thêm.

Một robot di chuyển trong một bảng lưới ô vuông kích thước ~m \times n~. Ô ở dòng ~i~ và cột ~j~ kí hiệu ~(i, j)~. Khi di chuyển đến ô ~(i, j)~, năng lượng của robot được tăng thêm ~a_{ij}~ đơn vị. Robot xuất phát từ ô ~(1, 1)~ và di chuyển đến ô ~(m, n)~. Tại mỗi bước, robot chỉ được phép di chuyển sang ô chung cạnh bên phải hoặc ô chung cạnh bên dưới. Để kích hoạt cổng thoát tại ô ~(m, n)~ và hoàn thành lộ trình, tổng năng lượng mà robot thu thập được trên toàn bộ lộ trình là lớn nhất và chia hết cho ~k~.

Yêu cầu: Tìm tổng năng lượng lớn nhất mà robot nhận được trên lô trình thỏa yêu cầu.

Input

Dòng đầu tiên chứa 3 số nguyên dương ~m, n, k~ (~1 \le m, n \le 500; 1 \le k \le 200~).

Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa ~n~ số nguyên, số thứ ~j~ là ~a_{ij}~ (~1 \le a_{ij} \le 10^6~).

Output

Một số nguyên là tổng năng lượng lớn nhất chia hết cho ~k~. Nếu không tồn tại lộ trình thỏa yêu cầu thì in ra -1.

Sample Input 1

5 7 11
2 5 3 1 8 4 6
7 1 9 2 5 3 1
4 6 2 8 1 7 5
9 3 5 1 4 2 8
1 7 4 6 2 9 3

Sample Output 1

44

Sample Input 2

5 7 30
2 5 3 1 8 4 6
7 1 9 2 5 3 1
4 6 2 8 1 7 5
9 3 5 1 4 2 8
1 7 4 6 2 9 3

Sample Output 2

-1

Subtasks

• 20% số test: ~m, n, k \le 10~.
• 30% số test: ~m, n \le 500; k = 1~.
• 50% số test: không ràng buộc gì thêm.

Trong khu rừng già, chú khỉ KONG đang thực hiện một hành trình trên một đường thẳng từ thời điểm 0 đến thời điểm ~T~. KONG có hai chế độ di chuyển:

• Chế độ 1 (Leo trèo): tốc độ ~a~ mét/giây.
• Chế độ 2 (Đu dây): tốc độ ~b~ mét/giây.

KONG bắt đầu hành trình (thời điểm ~t=0~) với Chế độ 1. Trong hành trình, KONG nhận được ~n~ mệnh lệnh thay đổi chế độ. Mệnh lệnh thứ ~i~ cho biết: tại thời điểm ~t_i~, KONG chuyển sang chế độ ~m_i~ và duy trì chế độ đó cho đến khi nhận được mệnh lệnh tiếp theo hoặc đến hết thời điểm ~T~.

Yêu cầu: Cho ~Q~ truy vấn, mỗi truy vấn gồm 2 số nguyên ~L, R~ yêu cầu tính tổng quãng đường (đơn vị mét) mà KONG đã di chuyển từ giây thứ ~L~ đến giây thứ ~R~ (gồm cả giây ~L~ và giây ~R~).

Input

Dòng đầu tiên chứa 5 số nguyên dương ~n, T, Q, a, b~ (~1 \le n, Q \le 10^5; 1 \le T \le 10^9; 1 \le a, b \le 10^6~). ~n~ dòng tiếp theo, dòng thứ ~i~ chứa 2 số nguyên ~t_i~ và ~m_i~ (~0 \le t_i \le T; m_i \in \{1, 2\}~). Các ~t_i~ được cho theo thứ tự tăng dần. ~Q~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên ~L, R~ (~0 \le L < R \le T~).

Output

Gồm ~Q~ dòng, mỗi dòng chứa một số nguyên duy nhất là quãng đường tương ứng với truy vấn.

Sample Input 1

3 10 2 5 8
2 2
5 1
8 2
0 5
3 9

Sample Output 1

34
39

• Từ ~t=0~ đến ~t=2~ (2 giây): tốc độ 5, quãng đường ~2 \times 5 = 10~ mét.
• Từ ~t=2~ đến ~t=5~ (3 giây): tốc độ 8, quãng đường ~3 \times 8 = 24~ mét.
• Từ ~t=5~ đến ~t=8~ (3 giây): tốc độ 5, quãng đường ~3 \times 5 = 15~ mét.
• Từ ~t=8~ đến ~t=9~ (1 giây): tốc độ 8, quãng đường ~1 \times 8 = 8~ mét.

1. Truy vấn ~[0, 5]~: Quãng đường là ~10 + 24 = 34~.
2. Truy vấn ~[3, 9]~:
   • Từ ~t=3~ đến ~t=5~ (2 giây): tốc độ ~8 \rightarrow 16~ mét.
   • Từ ~t=5~ đến ~t=8~ (3 giây): tốc độ ~5 \rightarrow 15~ mét.
   • Từ ~t=8~ đến ~t=9~ (1 giây): tốc độ ~8 \rightarrow 8~ mét.

Tổng cộng: ~16 + 15 + 8 = 39~.

Subtasks

• 25% số test: ~a = b~.
• 25% số test: ~n, Q \le 1000~.
• 50% số test: không ràng buộc gì thêm.