Cho hai số nguyên dương ~a, b~.

Yêu cầu: Tìm số lập phương nguyên dương nhỏ nhất chia hết cho cả ~a~ và ~b~.

INPUT

Chứa số nguyên dương ~a~ và ~b~ (~1 \leq a, b \leq 10^3~).

OUTPUT

Số lập phương tìm được.

SAMPLE INPUT

4 6

SAMPLE OUTPUT

216

Trong buổi tập trung học sinh đầu năm học, có Bình muốn chụp ảnh ~N~ học sinh của mình đang đứng thành một hàng được đánh số từ ~1~ đến ~N~ theo thứ tự từ trái qua phải. Một bức ảnh có thể chụp được một đoạn liên tiếp các học sinh trong một hàng. Mỗi học sinh phải có mặt trong ít nhất một bức ảnh.

Tuy vậy, trong hàng lại có ~K~ cặp học sinh ghét nhau tới nỗi hai học sinh trong cùng một cặp không muốn xuất hiện trong cùng một bức ảnh. Cho biết các cặp học sinh ghét nhau, hãy tính xem cô Bình cần chụp ít nhất bao nhiêu bức ảnh.

INPUT

Dòng đầu tiên gồm hai số nguyên ~N~ và ~K~ (~2 \leq N \leq 10^9~, ~1 \leq K \leq 1000~).

~K~ dòng tiếp theo, dòng thứ ~i~ chứa hai số ~a_i~ và ~b_i~ cho biết một cặp học sinh ghét nhau và không muốn xuất hiện chung trong một bức ảnh.

OUTPUT

Một số nguyên là số bức ảnh mà cô Bình cần phải chụp.

SAMPLE INPUT

8 3
1 4
2 3
5 6

SAMPLE OUTPUT

3

Giải thích: Cô Bình cần phải chụp 3 bức ảnh:

• Tấm thứ nhất gồm học sinh ~1, 2~.
• Tấm thứ hai gồm học sinh ~3, 4, 5~.
• Tấm thứ ba gồm học sinh ~6, 7, 8~.

Cho hai dãy số nguyên ~a_1, a_2, \ldots, a_n~ và ~c_1, c_2, \ldots, c_n~, với mọi ~1 \leq i \leq n~ ta có ~0 \leq a_i < k~.

Đếm số cặp (~x, y~) (~1 \le x < y \le n~) sao cho ~a_x = a_y~ và ~min~ (~c_x, c_{x + 1}, ..., c_y~) ~\le p~.

INPUT

• Dòng đầu chứa số nguyên ~n, k, p~ (~2 \leq n \leq 2 \times 10^6~, ~0 < k \leq 10^4~, ~0 \leq p \leq 100~).
• ~n~ dòng tiếp theo, dòng thứ ~t~ chứa hai số nguyên ~a_i~ và ~c_i~ (~1 \leq c_i \leq 10^9~).

OUTPUT

Một số nguyên là số lượng cặp thỏa mãn.

SUBTASKS

• Có ~25 \%~ số điểm có ~n \leq 10^2~.
• ~15 \%~ số điểm có ~n \leq 10^3~.
• ~40 \%~ số điểm có ~n \leq 2 \times 10^5~, ~0 < k \leq 50~.
• ~20 \%~ số điểm không có ràng buộc gì thêm.

SAMPLE INPUT

5 2 2
0 4
1 3
0 2
0 5
1 2

SAMPLE OUTPUT

4

An có ~n~ lá bài, lá bài thứ ~i~ (~1 \leq i \leq n~) có màu ~c_i~ và có giá trị là ~v_i~, tổng cộng có không quá ~k~ màu.

Các lá bài được đặt lần lượt theo thứ tự từ 1 tới ~n~ vào một hàng. Nếu ở lượt đặt thứ ~i~, lá bài thứ ~i~ có màu trùng với một lá bài nào đó đang nằm trên hàng, An có thể chọn bỏ tất cả các lá bài nằm giữa lá ~i~ và một lá bất kỳ đang nằm trên hàng cùng màu với lá ~i~ (việc bỏ bao gồm bỏ cả hai lá này), rồi nhận được số điểm bằng với tổng giá trị của những lá bài bị bỏ ra.

Yêu cầu: Hãy giúp An tìm chiến thuật để nhận được số điểm là lớn nhất.

INPUT

• Dòng đầu tiên chứa hai số nguyên ~n~, ~k~ (~1 \leq n, k \leq 10^6~).
• Dòng thứ hai chứa ~n~ số nguyên, số nguyên thứ ~i~ là ~c_i~ (~1 \leq c_i \leq k~).
• Dòng thứ ba chứa ~n~ số nguyên, số nguyên thứ ~i~ là ~v_i~ (~1 \leq v_i \leq 10^9~).

OUTPUT

Một số nguyên duy nhất là số điểm lớn nhất có thể nhận được.

SUBTASKS

• ~15\%~ số điểm có ~1 \leq n, k \leq 15~, ~c_i = v_i~.
• ~15\%~ số điểm có ~1 \leq n, k \leq 300~, ~c_i = v_i~.
• ~30\%~ số điểm có ~1 \leq n, k \leq 3 \times 10^3~.
• ~15\%~ số điểm có ~1 \leq n, k \leq 2 \times 10^5~.
• ~10\%~ số điểm có ~c_i = v_i~.
• ~15\%~ số điểm không có ràng buộc gì thêm.

SAMPLE INPUT

6 3
1 2 1 3 3 2
1 2 1 3 3 2

SAMPLE OUTPUT

11

Cho đồ thị có hướng không có cạnh nối từ một đỉnh đến chính nó, không có cạnh lặp, có trọng số gồm ~n~ đỉnh và ~m~ cạnh. Gọi ~d~ là độ dài đường đi ngắn nhất từ đỉnh ~1~ tới đỉnh ~n~. Đếm số lượng đường đi từ ~1~ tới ~n~ có độ dài không quá ~d + k~. Vì kết quả có thể rất lớn nên kết quả trả về là số dư của nó với số nguyên ~MOD~.

INPUT

Dòng đầu tiên chứa số nguyên ~T~ (~T > 0~), tương ứng với số lượng test case.

Với mỗi test case được đưa ra:

• Dòng đầu tiên chứa bốn số nguyên ~n, m, k, MOD~ (~n, m > 0~, ~k ≥ 0~, ~1 ≤ MOD ≤ 10^9~).
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~a_i~, ~b_i~, ~c_i~ (~1 ≤ a_i, b_i ≤ n~, ~0 \le c_i \le 10^3~) tương ứng với cạnh nổi từ đinh ~a_i~ đến ~b_i~ có trọng số ~c_i~.
• Dữ liệu đảm bảo tồn tại ít nhất một đường đi từ ~1~ tới ~n~.

OUTPUT

Với mỗi test case, ghi ra một số nguyên là kết quả trả về với test case đó trên một dòng. Nếu có vô số đường đi thoả mãn, kết quả trả về ~-1~.

SAMPLE INPUT

1
4 4 2 998244353
1 2 1
2 4 1
2 3 2
3 4 1

SAMPLE OUTPUT

2

SUBTASKS

• ~10 \%~ số điểm có ~T ≤ 5~, ~2n, m ≤ 10~, ~k = 0~, không có cạnh trọng số ~0~.
• ~30 \%~ số điểm có ~T ≤ 5~, ~2n, m ≤ 2 \times 10^3~, ~k = 0~, không có cạnh trọng số ~0~.
• ~10 \%~ số điểm có ~T ≤ 5~, ~2n, m ≤ 2 \times 10^3~, ~k \le 50~, không có cạnh trọng số ~0~.
• ~10 \%~ số điểm có ~T ≤ 5~, ~2n, m ≤ 2 \times 10^3~, ~k \le 50~.
• ~10 \%~ số điểm có ~T ≤ 5~, ~2n, m ≤ 2 \times 10^5~, ~k = 0~, không có cạnh trọng số ~0~.
• ~10 \%~ số điểm có ~T ≤ 3~, ~2n, m ≤ 2 \times 10^5~, ~k \le 50~, không có cạnh trọng số ~0~.
• ~20 \%~ số điểm có ~T ≤ 3~, ~2n, m ≤ 2 \times 10^5~, ~k \le 50~.