Dù ngày mai phải kiểm tra môn Ngữ Văn và Tiếng Anh, anh LVT vẫn không thèm học bài vì đối với anh, mấy môn này quá đơn giản. Thay vào đó, anh LVT lại bày ra trò chơi như sau:

Anh bày ra ~n~ đồng xu, được đánh số từ ~1~ tới ~n~ và ban đầu tất cả các đồng xu đều ở mặt ngửa. LVT sẽ lần lượt chơi từ đồng xu thứ ~1~ tới đồng xu thứ ~n~. Ở đồng xu thứ ~i~, anh sẽ thay đổi trạng thái của các đồng xu có số thứ tự là bội của ~i~. Nếu đồng xu đó đang ở trạng thái sấp thì anh sẽ đổi thành ngửa và ngược lại.

Anh LVT muốn biết sau khi chơi xong ~n~ đồng xu theo thứ tự, thì có bao nhiêu đồng xu có mặt sấp? Nhưng bây giờ anh LVT đang bận kéo người yêu leo rank cao thủ Liên Quân Mobile nên chưa rảnh để tính được. Các bạn hãy giúp anh LVT nhé!

Input

• Đọc từ file LDX.INP một số nguyên dương ~n~ là số lượng đồng xu anh LVT bày ra.

Output

• Ghi ra file LDX.OUT một số nguyên ~k~ là số lượng đồng xu có mặt sấp sau khi thực hiện ~n~ lượt chơi.

Giới hạn

• 30% số test có ~n \le 10^6~
• 30% số test có ~n \le 10^{12}~
• 40% số test có ~n \le 10^{18}~

Ví dụ

Sample input

3

Sample output

1

Giải thích ví dụ

Trạng thái các đồng xu sau từng lượt chơi, với ~'N'~ biểu thị đồng xu đang ở mặt ngửa, ~'S'~ biểu thị đồng xu đang ở mặt sấp:

• Ban đầu: ~(N,N,N)~
• Sau lượt ~1~: ~(S,S,S)~
• Sau lượt ~2~: ~(S,N,S)~
• Sau lượt ~3~: ~(S,N,N)~

Do đó, sau ~3~ lượt chỉ có ~1~ đồng xu ở trạng thái sấp

Kí hiệu ~N!~ (đọc là ~N~ – giai thừa) là tích các số tự nhiên bắt đầu từ ~1~ đến ~N~. Cho hai số nguyên dương ~N~ và ~P~ trong đó ~P~ là số nguyên tố không vượt quá ~N~.

Yêu cầu: Tìm số nguyên dương ~K~ lớn nhất sao cho ~P^K~ là ước của ~N!~

Input

• Dòng thứ nhất chứa số ~N~
• Dòng thứ hai chứa số ~P~

Output

• Số ~K~ lớn nhất theo yêu cầu

Giới hạn

• 100% số test có ~n \le 10^9~

Ví dụ

Sample input

19 3

Sample output

8

Bạn được cho một dãy ~A~ chứa ~N~ số nguyên và ~Q~ truy vấn. Mỗi truy vấn được thể hiện bằng hai số nguyên ~L~ và ~R~. Với mỗi truy vấn, in ra số bộ ba ~(i~, ~j~, ~k)~ sao cho ~(L ≤ i < j < k ≤ R)~ và ~(A_i + A_j + A_k)~ là một số chẵn.

Input

• Đọc từ file BBTC.INP:

  • Dòng đầu tiên chứa số nguyên ~N~, ~Q~. ~(1 ≤ N~, ~Q ≤ 10^5)~

  • Dòng tiếp theo chứa ~N~ số nguyên, số nguyên thứ ~i~ có giá trị ~A_i~. ~(0 ≤ A_i ≤ 10^6)~

  • ~Q~ dòng tiếp theo mỗi dòng chứa ~2~ số nguyên ~L_i~, ~R_i~. ~(1 ≤ L_i ≤ R_i ≤ N)~

Output

• Ghi ra file BBTC.OUT gồm ~Q~ dòng, mỗi dòng sẽ chứa số lượng bộ ba được nói đến trong đề bài.

Sample Input

6 3
1 2 3 4 5 6
1 3
2 5
1 6

Sample Output

1
2
10

Giải thích

• Với truy vấn đầu tiên, ta sẽ chọn bộ ~(1~, ~2~, ~3)~ vì ~A_1 + A_2 + A_3 = 6~ là một số chẵn.

• Với truy vấn thứ hai, ta sẽ chọn ~2~ bộ: bộ ~(2~, ~3~, ~5)~ vì ~A_2 + A_3 + A_5 = 10~ là một số chẵn và bộ ~(3~, ~4~, ~5)~ vì ~A_3 + A_4 + A_5 = 12~ là một số chẵn.

Cho mảng ~A~ gồm ~N~ phần tử, mảng ~B~ gồm ~M~ phần tử. (~1 \le N, M \le 10^5~).

Hãy tạo ra một dãy không giảm: ~A_1 \le A_2 \le ... \le A_i \le B_j \le B_{j + 1} \le ... \le B_M~.

Lưu ý: Dãy bạn tạo là dãy gồm ~i~ phần tử đầu tiên của mảng ~A~ (~1 \le i \le N~) và ~j~ phần tử cuối của mảng ~B~ (~1 \le j \le M~).

Tìm dãy có kích thước lớn nhất.

Input

• Dòng đầu tiên ghi số nguyên dương ~N~.
• Dòng thứ hai ghi ~N~ số nguyên: ~A_1, A_2, ..., A_N~. ~(-10^9 \le A_i \le 10^9)~
• Dòng thứ ba ghi số nguyên dương ~M~.
• Dòng cuối cùng ghi ~M~ số nguyên: ~B_1, B_2, ..., B_M~. ~(-10^9 \le A_i \le 10^9)~

Output

• Gồm ~1~ dòng ghi số nguyên là kích thước lớn nhất trong các dãy tìm được.

Giới hạn

• 50% số test có ~N, M \le 10^3~
• 50% số test còn lại có ~N, M \le 10^5~

Ví dụ

Sample input

3
1 4 9
4
5 2 4 5

Sample output

4

Giải thích ví dụ

Có ~2~ dãy tìm được là:

~1~ ~2~ ~4~ ~5~

~1~ ~4~ ~4~ ~5~

Và hai dãy này đều có độ dài là ~4~.