Giải trí

Bạn được cho các số nguyên dương \(a, b\) \((1 \leq a, b \leq 10)\).

Yêu cầu: Hãy chọn số nguyên dương \(c\) nằm trong khoảng từ \(1\) đến \(10\) sao cho \(a \times b \times c\) là một số lẻ.

Ví dụ:

• \(a=1, b=5\), ta chọn số \(c=3\) thì \(a \times b \times c = 15\) là số lẻ
• \(a=8, b=3\), thì không chọn được số nào để \(a \times b \times c\) là số lẻ

Input

• Dòng thứ nhất chứa số nguyên dương \(a\) \((1 \leq a \leq 10)\).
• Dòng thứ hai chứa số nguyên dương \(b\) \((1 \leq b \leq 10)\).

Output

• Nếu chọn được số \(c\) để \(a \times b \times c\) là số lẻ thì in ra chữ Y, ngược lại in chữ N.

Example

3
4

N

5
7

Y

Bạn được cho các số nguyên dương \(k\) \((1 \leq k \leq 1.000.000.000)\).

Yêu cầu: Hãy tìm số cách chọn khác nhau cặp số gồm một số chẵn và một số lẻ trong các số từ 1 đến \(k\) (Thứ tự không quan trọng: \((1,4)\) và \((4,1)\) được tính là một cặp).

Ví dụ: \(k=4\), ta chọn được 4 cặp khác nhau là \((1,2);(1,4);(2,3);(3,4)\).

Input

• Một dòng chứa số nguyên dương \(k\) \((1 \leq k \leq 1.000.000.000)\).

Output

• In ra số cách chọn các cặp.

Example

3

2

5

6

Bạn được cho trước các số nguyên \(n, k\). Tìm số lượng bộ ba số \((a, b, c)\) với \(1 \leq a, b, c \leq n\) sao cho \(a + b\), \(b + c\) và \(c + a\) đều là bội của \(k\). Hai bộ ba số được gọi là khác nhau nếu chỉ cần một số cùng vị trí trong chúng khác nhau: \((1, 3, 3)\) khác \((3, 1, 3)\) vì có đến 2 vị trí khác nhau.

Ví dụ:

• \(n = 5, k = 3\), ta chọn được \(1\) cặp thỏa mãn là \((3, 3, 3)\)
• \(n = 3, k = 2\), ta chọn được \(9\) cặp thỏa mãn là \((1,1,1), (1,1,3), (1,3,1), (1,3,3), (2,2,2), (3,1,1), (3,1,3), (3,3,1), (3,3,3)\)

Input

• Dòng thứ nhất chứa số nguyên dương \(n\) \((1 \leq n \leq 200.000)\).
• Dòng thứ hai chứa số nguyên dương \(k\) \((1 \leq k \leq 200.000)\).

Output

• In ra số bộ ba số \((a, b, c)\) thỏa mãn yêu cầu.

Example

5
3

1

3
2

9

Bạn có \(N\) chiếc đèn xếp thẳng hàng, được đánh dấu vị trí từ 1 đến \(N\). Ta sẽ thực hiện \(N\) thao tác. Thao tác thứ \(i\) sẽ thay đổi trạng thái từ bật thành tắt và ngược lại từ tắt thành bật của những bóng đèn ở vị trí chia hết cho \(i\). Ban đầu tất cả bóng đèn đều ở trạng thái tắt.

Yêu cầu: Sau khi thực hiện \(N\) thao tác bạn có \(Q\) câu hỏi, câu hỏi thứ \(i\) có dạng \(Q(L,R)\) có nghĩa là trong đoạn [\(L,R\)] có bao nhiêu bóng đèn đang bật.

Dữ liệu

• Dòng đầu tiên gồm hai số \(N,Q\) (\(1≤N ≤10^{18},Q≤10^5\)).
• \(Q\) dòng tiếp theo, mỗi dòng gồm hai số \(L,R\) (\(1≤L ≤ R≤N\)).

Kết quả

• Ghi ra \(Q\) dòng, mỗi dòng là số lượng bóng đèn đang bật cho từng câu hỏi

Input

5 2
1 5
2 4

Output

2
1

Ràng buộc

• 20% số test: \(1≤N,Q≤10^3\).
• 20% số test: \(1≤N,Q≤10^5\).
• 60% số test: không có giới hạn gì thêm.

Nguồn: TS10LQĐ