Cho số nguyên dương ~n~ (~1 \le n \le 10^{18}~).

Yêu cầu: Tìm số nguyên lớn nhất không vượt quá ~n~ và là tích của ~3~ số nguyên tố liên tiếp.

Dữ liệu vào từ tệp BAI1.INP

• Dòng đầu tiên chứa số nguyên dương ~t~ tương ứng là số bộ test (~1 \le t \le 15~);
• Trong ~t~ dòng tiếp theo mỗi dòng chứa số nguyên dương ~n~.

Kết quả ra ghi vào tệp BAI1.OUT

Gồm ~t~ dòng là kết quả của ~t~ bộ test tương ứng, nếu không tìm thấy số thỏa mãn ghi ~-1~.

Ví dụ

Input

1
36

Output

30

Giải thích: ~30 = 2 \times 3 \times 5~

Lưu ý: ~50\%~ số test ứng với ~50\%~ số điểm của bài có ~n \le 10^6~

Để thay đổi không khí sau những ngày làm việc căng thẳng, An dự định sẽ đi du lịch trong ~n~ ngày bằng xe riêng của mình. Ngày thứ ~i~, xe cần ~a_i~ lít xăng, (~1 \le i \le n~). Mỗi ngày An có thể mua số lượng xăng không hạn chế, nếu không dùng hết có thể để dành cho những ngày tiếp theo.

Yêu cầu: Hãy giúp An quyết định lượng xăng mua mỗi ngày để đáp ứng yêu cầu với tổng số tiền phải trả là ít nhất có thể.

Dữ liệu vào từ tệp BAI2.INP

• Dòng đầu chứa số nguyên dương ~n~ (~n \le 10^5~);
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i \le 10^5, 1 \le i \le n~);
• Dòng thứ ba chứa ~n~ số nguyên dương ~p_1, p_2, ..., p_n~ (~p_i \le 10^5, 1 \le i \le n~);

Kết quả ra ghi vào tệp BAI2.OUT

Một số nguyên duy nhất là tổng số tiền phải trả (tính bằng đồng) để mua xăng theo phương án tìm được.

Ví dụ

Input

3
1 2 3
3000 1000 3000

Output

8000

Giải thích: Ngày ~1~ mua ~1~ lít (~3000~đ), ngày ~2~ mua ~5~ lít (~5000~đ), ngày ~3~ mua ~0~ lít (~0~đ)

Lưu ý: ~50\%~ số test ứng với ~50\%~ số điểm của bài có ~n \le 10^3~.

Cho dãy gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~. Với mỗi dãy con ~a_l, a_{l+1}, ..., a_r~ (~1 \le l \le r \le n~), và số nguyên dương ~s~, gọi ~k_s~ là số lần xuất hiện của ~s~ trong dãy con ~a_l, a_{l+1}, ..., a_r~. Giá trị của dãy còn trên được tính bằng tổng của tất cả các tích ~(k_s)^2 \times s~.

Ví dụ, cho dãy gồm ~8~ số nguyên dương ~1, 1, 2, 2, 1, 3, 1, 1~. Dãy con với ~l = 2, r = 7~ có ~k_1 = 3, k_2 = 2, k_3 = 1~ còn ~s > 3~ thì ~k_s = 0~. Từ đó giá trị của dãy con là ~3^2 \times 1 + 2^2 \times 2 + 1^2 \times 3 = 20~.

Yêu cầu: Cho ~t~ dãy con, hãy xác định giá trị của mỗi dãy.

Dữ liệu vào từ tệp BAI3.INP

• Dòng đầu chứa hai số nguyên ~n~ và ~t~ (~1 \le n \le 2 \times 10^5, 1 \le t \le 2 \times 10^5~);
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ...,a_n~ (~1 \le a_i \le 10^6~);
• Trong ~t~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~l~ và ~r~ (~1 \le l \le r \le n~) mô tả một dãy con.

Kết quả ra ghi vào tệp BAI3.OUT:

Gồm ~t~ dòng, dòng thứ ~k~ ghi một số nguyên là giá trị của dãy con thứ ~k~ (~1 \le k \le t~).

Ví dụ

Input

3 2
1 2 1
1 2
1 3

Output

3
6

Giải thích:

• ~3 = 1^2 \times 1 + 1^2 \times 2~
• ~6 = 2^2 \times 1 + 1^2 \times 2~

Lưu ý: ~50\%~ số test ứng với ~50\%~ số điểm của bài có ~n \le 2000, t \le 2000~.

Trong một hội nghị quốc tế có ~m~ đại biểu tham dự được đánh số từ ~1~ đến ~m~. Tại hội nghị có sử dụng ~n~ ngôn ngữ khác nhau được đánh số từ ~1~ đến ~n~. Mỗi đại biểu biết một số ngôn ngữ trong ~n~ ngôn ngữ đó. Hai đại biểu ~u~ và ~v~ có thể trao đổi với nhau nếu biết một ngôn ngữ chung hoặc nhờ các đại biểu khác làm phiên dịch.

Khi một đại biểu ~u~ muốn chào đại biểu ~v~, đại biểu ~u~ sẽ nói to lời chào bằng một ngôn ngữ ~i~ mà đại biểu này biết và các đại biểu biết ngôn ngữ ~i~ đều hiểu được lời chào này. Nếu đại biểu ~v~ không hiểu lời chào đó (~v~ không biết ngôn ngữ ~i~), có một số đại biểu khác phiên dịch trung gian để đại biểu ~v~ hiểu được lời chào từ đại biểu ~u~. Gọi ~a_{uv}~ là số đại biểu có thể hiểu được lời chào của đại biểu ~u~ dành cho đại biểu ~v~.

Yêu cầu: Với mỗi cặp ~u, v~ (~1 \le u \le m, 1 \le v \le m~), xác định số dương ~a_{uv}~ nhỏ nhất.

Dữ liệu vào từ tệp BAI4.INP:

• Dòng đầu chứa hai số nguyên dương ~m~ và ~n~ (~2 \le m \le 300, 1 \le n \le 300~);
• Trong ~m~ dòng tiếp theo, dòng thứ ~i~ (~1 \le i \le m~) chứa số nguyên dương ~k_i~ là số lượng các ngôn ngữ mà đại biểu ~i~ biết, tiếp theo là số ~k~, số hiệu các ngôn ngữ đó theo thứ tự tăng (~1 \le k_i \le n~).

Kết quả ra ghi vào tệp BAI4.OUT:

Gồm ~m~ dòng và ~m~ cột. Tại vị trí dòng thứ ~u~, cột thứ ~v~ ghi số ~a_{uv}~ tìm được (~1 \le u \le m, 1 \le v \le m~). Trong đó ~a_{uu} = 0~. Nếu hai đại biểu ~u~ và ~v~ không thể hiểu lời chào của nhau thì ~a_{uv} = -1~.

Ví dụ:

Input

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

Output

0 2 3 3
2 0 2 4
3 2 0 3
3 4 3 0

Giải thích:

• Đại biểu ~1~ chào đại biểu ~2~ bằng ngôn ngữ ~1~ có hai đại biểu hiểu lời chào là ~1~ và ~2~.
• Đại biểu ~1~ chào đại biểu ~2~ bằng ngôn ngữ ~3~. Sau đó đại biểu ~3~ phiên dịch sang ngôn ngữ ~2~ để đại biểu ~2~ hiểu được. Tất cả ~4~ đại biểu đều hiểu lời chào.

Từ đó ~a_{12} = a_{21} = 2~.

Lưu ý: ~50\%~ số test ứng với ~50\%~ số điểm của bài có ~2 \le m \le 100, 1 \le n \le 100~.