Bạn Phú đang ôn luyện việc tính độ phức tạp của thuật toán để ra Tết có thể đi phỏng vấn intern công ty công nghệ. Việc đánh giá độ phức tạp có thể thực hiện thông qua việc đếm số thao tác tính toán căn bản. Bạn ấy muốn đếm theo ~n~ số phép gán biến và số phép so sánh trong đoạn code bên dưới, hãy giúp bạn ấy nhé.

Input

Một số nguyên dương ~n~ duy nhất với ~1 \le n \le 10^5.~

Output

Số phép so sánh và số phép gán biến cần để thực hiện đoạn code (tính theo ~n~).

Sample input

16

Sample output

155 439

Dưới đây là đoạn code đang xét:

int i = 1, res = 0;
while(i <= n){
    int j = 1, k = 1;
    while(j <= i*i*i){
        j = j + k;
        k = k + 1;
        res = res + 1;
    }
    if(j % 2 == 0){
        res = res - j*k;
    }
    else{
        res = res + j*k;
    }
    i = i + i;
}

Thầy Tina muốn SV trong CLB H3.2 ôn luyện Olympic xuyên Tết rất căng thẳng. Vì thế nên các bạn không dám công khai đón Tết mà chỉ dám chúc mừng năm mới nhau thông qua các tin nhắn đã mã hóa. Một tin nhắn là có lời chúc mừng nếu nó có chữ ~C~, ~M~, ~N~, ~M~ (chúc mừng năm mới) theo đúng thứ tự đó nhưng không nhất thiết liên tiếp. Bây giờ cho danh sách của một vài câu nói giữa các thành viên trong CLB, hãy kiểm tra xem câu nào có lời chúc mừng bí mật đó nhé.

Input

Dòng đầu tiên gồm số ~t~ là số câu với ~1 \le t \le 5.~

Trong ~t~ dòng tiếp theo, mỗi dòng là một câu có độ dài không quá ~10^5.~

Output

Với mỗi câu, in ra YES nếu nó có chứa lời chúc, ngược lại in ra NO.

Sample input

5
CMND
CMCM
CMNM
XXXXX
COMOTCHANGNGHESILOMO

Sample output

NO
NO
YES
NO
YES

Vào ngày Tết, mâm trái cây chưng lên bàn thờ là một loại không thể thiếu. Thường thì người ta sẽ bày 5 loại trái cây với nhiều ý nghĩa khác nhau. Các bạn sinh viên của H3.2 thì thích chưng 5 loại trái cây sau đây:

Mãng cầu, Dừa, Đu đủ, Khổ qua, Khoai môn => Cầu vừa đủ qua môn.

Các sinh viên nhờ thầy Luna đi ra chợ Gò Vấp mua đủ 5 loại này nhưng thầy chỉ mới tìm được có hai quả tròn thôi (nó là hình cầu nhưng khi nhìn từ trên xuống sẽ là hình tròn nên tạm coi là hình tròn). Sinh viên đi thêm chợ Bà Chiểu để mua thêm một quả hình chữ nhật (nó là hình hộp nhưng khi nhìn từ trên xuống sẽ là hình chữ nhật nên tạm coi là hình chữ nhật) để chưng thêm cho vui hơn. Khi chưng lên mâm thì quả tròn to sẽ đặt trên, rồi đến quả hình chữ nhật và rồi quả tròn nhỏ, xem hình minh họa để hiểu rõ hơn.

Câu hỏi đặt ra là: cho thông tin kích thước của quả tròn to và quả tròn nhỏ, đếm số cách chọn kích cỡ cho quả hình chữ nhất nằm giữa hai quả đó.

Input

Một dòng duy nhất gồm số nguyên ~R_1, R_2~ với ~1 \le R_1 < R_2 \le 10^6~ với ~R_1~ là đường kính của quả tròn nhỏ và ~R_2~ là bán kính của quả tròn to.

Output

Đếm số cách chọn ra cặp số ~(a,b)~ nguyên dương và ~a \le b~ là kích thước của quả hình chữ nhật sao cho có thể đặt quả này lên trên quả tròn to và đặt được dưới quả tròn nhỏ.

Sample input 1

1 3

Sample output 1

13

Giải thích: ta có thể chọn các kích thước là: ~(1,1), (1,2), (1,3), (1,4), (1,5), (2,2), (2,3), (2,4), (2,5), (3,3), (3,4), (3,5), (4,4),~ bạn có thể tự vẽ hình ra để hiểu rõ hơn.

Subtasks

• Có 50% test ứng với ~n \le 2023~.
• Có 50% test ứng với ~2024 \le n \le 10^6.~

Vào ngày mùng 1 Tết, Vũ vì ham chơi nên đã quên lì xì cho bạn gái của mình và chuyện gì đến rồi cũng đã đến: bạn gái của anh ấy muốn kết thúc cuộc tình của hai người tại đây vì hành động sơ ý đó của chàng trai. Tuy nhiên, vì là một người đã cô đơn rất lâu rồi và giờ mới có được một mảnh tình vắt vai nên Vũ đã năn nỉ, thuyết phục cô bạn gái tha thứ cho mình. Bạn gái của anh ta đã đồng ý tha thứ cho anh ấy với điều kiện là anh ta phải giải được một mê cung tình ái mà cô ấy ra cho anh, nếu không thì Vũ sẽ chính thức trở thành một thằng thiếu nữ vĩnh viễn.

Mê cung tình ái này là một cái bảng có kích cỡ vô hạn như tình yêu em dành cho anh, với ô trên cùng bên trái có số 1. Hình bên là 5 lớp đầu tiên của mê cung. Cô ấy muốn Vũ tìm được giá trị ở ô tại hàng ~x~ và cột ~y~. Bạn hãy giúp Vũ cứu lấy cuộc tình của anh ấy nhé.

Input

Dòng đầu tiên chứa một số nguyên dương ~T~ với ~1 ≤T≤ 10^5~ là số lượng truy vấn.

Trong ~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x,y~ với ~1≤x,y≤10^9.~

Output

Trên mỗi dòng, in ra một số nguyên thể hiện giá trị của ô tại hàng ~x~ và cột ~y~.

Sample input

4
2 3
1 1
4 2
6 7

Sample output

8
1
15
44

Code camp Đà Lạt vào dịp cuối năm có ~n~ team tham gia. Các team được đánh số hiệu từ ~1~ đến ~n~, team thứ ~i~ có ~a_i~ học sinh. Trong buổi sinh hoạt tập thể, BTC muốn tổ chức cho sinh viên chơi trò chơi theo nhóm, mỗi nhóm có đúng ~k~ học sinh và không nhóm nào có hai học sinh cùng team (có thể có học sinh không được xếp vào bất cứ nhóm nào). Ban đầu, chỉ có ~m~ team có số hiệu ~1,2,…,m~ (với ~m<n~) tham gia. Mỗi một lượt chơi sau đó, các team có số hiệu ~m+1,m+2,…,n~ lần lượt đăng kí tham gia thêm. Mỗi khi có đoàn mới đăng kí tham gia, ban tổ chức sẽ sắp xếp lại các nhóm sao cho có nhiều nhóm chơi nhất theo quy định cũ như trước: mỗi nhóm có đúng ~k~ học sinh và không nhóm nào có hai học sinh cùng team.</p>

Yêu cầu làm giúp BTC tính ra số nhóm nhiều nhất có thể xếp được mỗi khi có team mới đăng ký tham gia chơi.

Input

Dòng đầu tiên ghi số nguyên dương ~T~ với ~T≤100~ tương ứng với ~T~ bộ dữ liệu, mỗi bộ theo dạng sau:

Dòng thứ nhất gồm ba số nguyên dương ~n,k,m~ với ~k,m<n \le 10^5~;</p>

Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~ với ~1≤a_i≤10^9,i= 1,2,…,n~

Output

In ra ~T~ dòng, mỗi dòng gồm ~n-m~ số nguyên, trong đó số thứ ~j~ là số nhóm tối đa xếp được khi team ~m+j~ đăng kí tham gia (trong đó ~j = 1,2,… n-m~).

Sample input

1
5 3 3
3 5 3 2 4

Sample output

4 5

Subtasks:

• Có ~30\%~ test với ~T = 1; k,m<n≤10^3;~</li>
• Có ~30\%~ test với ~T≤10; k,m<n≤10^3~</li>
• Có ~40\%~ test với ~T≤100; k,m<n≤10^5~.</li>

Để chào đón Tết 2024, shop cô Ban có đặt mua nhiều bánh tét về để bán trong CLB. Độ dài của bánh là một số nguyên dương ~n~ và các khách hàng của cô cũng là những người sành điệu. Họ thích làm số học, đặc biệt là số square-free lớn hơn ~1~ nên yêu cầu cô Ban phải cắt bánh ra thành các đoạn nhỏ có độ dài square-free thì mới mua, không thì sẽ bom hàng. Chú ý: số squareg-free là nguyên dương không có ước chính phương nào khác ~1~, ví dụ: ~2,3,6,10,...~ là các số như vậy, còn ~4,12,16,18,...~ thì không.

Câu hỏi đặt ra là với một khúc bánh có độ dài ~n~ thì cô có thể bán cho nhiều nhất và ít nhất mấy người?

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~1 \le n \le 10^{14}~ cho biết độ dài khúc bánh.

Output

Hai giá trị cho biết số người ít nhất và nhiều nhất mà cô có thể bán.

Sample input 1

1

Sample output 1

0 0

Sample input 2

8

Sample output 2

2 4

Giải thích: ở VD1, ta thấy độ dài khúc bánh là ~1~ thì không thể cắt nhỏ ra được nữa, còn với độ dài ~8~ thì có kiểu cắt thành: ~2+6~ hoặc ~2+2+2+2.~

Subtasks:

• Có 25% số test ứng với ~n \le 100.~
• Có 25% số test ứng với ~n \le 10^5.~
• Có 50% số test ứng với ~10^5 < n \le 10^{14}.~

Lịch đi du lịch ngày Tết của đại gia Tài sẽ gồm ~n~ thành phố và cho biết có ~m~ đường bay hai chiều giữa chúng. Hệ thống các đường bay có đặc biệt là giữa 2 thành phố bất kỳ luôn có một đường đi bao gồm một hoặc nhiều đường bay trực tiếp giữa hai thành phố. Trung tâm điều khiển không lưu đưa ra khái niệm độ ổn định giữa cặp hai thành phố ~A~ và ~B~ là số lượng đường bay trực tiếp mà việc bỏ đi một trong số chúng (các con đường khác vẫn thực hiện bình thường) dẫn đến không thể đi từ thành phố ~A~ đến thành phố ~B~ được nữa. Một nghiên cứu cho biết rằng, trong điều kiện thời tiết xấu, tổng ổn định kết giữa các cặp thành phố phải đạt đến một giá trị nhất định thì hệ thống đường đi mới được gọi là an toàn.

Tài đang băn khoăn rằng tổng độ ổn định của danh sách ~n~ địa điểm đi chơi của mình có đạt không để biết mà sắp xếp. Bạn hãy giúp Tài tính ra giá trị đó nhé.

Input

Dòng đầu tiên chứa hai số nguyên ~N, M~ với ~1≤N≤300000~ và ~1≤M≤300000.~

Mỗi dòng trong số ~N~ dòng tiếp theo chứa thông tin về một con đường, bao gồm hai số nguyên dương từ 1 đến ~N~: chỉ số của hai thành phố được nối bởi một con đường.

Output in ra 1 số nguyên duy nhất là tổng độ ổn định giữa mọi cặp thành phố.

Sample input

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

Sample output

10

Subtasks

• 30% số test tương ứng 30% số điểm có ~n<100.~
• 30% số test tương ứng 30% số điểm có ~n<10000.~
• 40% số test tương ứng với 40% số điểm không có dàng buộc gì thêm.