Cho một số nguyên không âm ~n~. Hãy hỏi có bao nhiêu cách chọn ra bộ 5 biến ~a, b, c, d, e~ là số nguyên không âm sao cho tổng lại bằng ~n~:

~a + b^2 + c^3 + d^2 + e = n~

Giới hạn

• ~0 \leq n \leq 200~

Đầu vào

• Dòng đầu tiên: số nguyên không âm ~n~.

Đầu ra

• Một số nguyên duy nhất: số cách chọn ra bộ 5 biến không âm sao cho tổng bằng ~n~.

Sample Input

5

Sample Output

44

Nhập vào một mảng ~a~ gồm ~n~ phần tử.

Tìm giá trị lớn nhất của biểu thức sau:

~|a_i - a_j| + |a_j - a_k| + |a_k - a_l| + |a_l - a_i|~

Với ~1 \leq i, j, k, l \leq n~ và ~i, j, k, l~ phân biệt nhau.

Giới hạn

• ~4 \leq n \leq 100~
• ~-10^6 \leq a_i \leq 10^6~

Đầu vào

• Dòng đầu tiên: số nguyên ~n~.
• Dòng thứ hai: ~n~ số nguyên ~a_i~.

Đầu ra

• Một số nguyên duy nhất: giá trị lớn nhất của biểu thức.

Sample Input

5
1 2 3 4 5

Sample Output

12

Cho một chuỗi ~s~ gồm ~n~ ký tự. Nhiệm vụ của bạn là đếm số lượng chuỗi con đối xứng (hay còn gọi là chuỗi palindrome) trong chuỗi này. Một chuỗi con đối xứng là chuỗi mà nếu đọc từ trái sang phải và từ phải sang trái đều giống nhau. Hãy khám phá chuỗi này và tìm ra những chuỗi con đối xứng ẩn giấu bên trong.

Giới hạn

• ~1 ≤ n ≤ 200~
• ~s~ chỉ bao gồm các ký tự chữ cái Latin viết thường.

Đầu vào

• Dòng đầu tiên: chuỗi ~s~

Đầu ra

• Một số nguyên duy nhất: số lượng chuỗi con đối xứng trong ~s~.

Sample Input

ababa

Sample Output

9

Giải thích

Trong chuỗi "ababa", các chuỗi con đối xứng là:

• Ký tự đơn lẻ: a, b, a, b, a (5 chuỗi).
• Chuỗi dài hơn: aba, bab, aba, ababa (4 chuỗi).
• Tổng cộng, số lượng chuỗi con đối xứng là 9.

Cho một chuỗi ký tự, bạn được giao nhiệm vụ loại bỏ tất cả các ký tự trùng lặp liên tiếp trong chuỗi. Chỉ giữ lại ký tự đầu tiên trong mỗi nhóm ký tự trùng lặp.

Giới hạn

• Chiều dài chuỗi không vượt quá ~10^5~.
• Các ký tự chỉ bao gồm các chữ cái Latin viết thường.

Đầu vào

• Một chuỗi ký tự ~S~.

Đầu ra

• Chuỗi ký tự sau khi loại bỏ các ký tự trùng lặp liên tiếp.

Sample Input

aabbbbcccaa

Sample Output

abca

Cho một mảng ~a~ gồm ~n~ phần tử, hãy tính tổng các số chẵn và tổng các số lẻ trong đoạn từ ~l~ đến ~r~ của mảng, trong đó chỉ số mảng được tính từ 1.

Giới hạn

• ~1 ≤ a_i ≤ 10^9~
• ~1 ≤ n ≤ 2 \times 10^5~
• ~1 ≤ l < r ≤ n~

Đầu vào

• Dòng đầu tiên: số nguyên ~n~
• Dòng thứ hai: ~n~ số nguyên ~a_i~, cách nhau bởi khoảng trắng
• Dòng thứ ba: hai số nguyên ~l~ và ~r~, cách nhau bởi khoảng trắng

Đầu ra

• Hai số nguyên cách nhau bởi khoảng trắng: tổng lẻ và tổng chẵn trong đoạn từ ~l~ đến ~r~

Sample Input

6
1 2 3 4 5 6
2 5

Sample Output

8 6

Số nguyên tố, gạch xây toán học
Ước số chúng, đếm đếm tỉ mỉ
Hai, ba, năm - những viên gạch nhỏ
Xếp chồng lên nhau, tạo nên kỳ tích
Phân tích số, tìm ra yếu tố
Đếm từng ước, nguyên tố hiện hình
Thuật toán chạy, con số hiển lộ
Bí ẩn toán học, dần dần sáng tỏ

Có một số nguyên dương ~n~ mang theo nhiều bí ẩn. Các số từ 1 đến ~n~ không chỉ đóng vai trò là ước của ~n~, mà một số trong đó còn là những số nguyên tố đặc biệt. Nhiệm vụ của bạn là tìm ra bao nhiêu số trong đoạn từ 1 đến ~n~ vừa là ước của ~n~, vừa là số nguyên tố.

Giới hạn

• ~1 ≤ n ≤ 10^6~

Đầu vào

• Dòng đầu tiên: số nguyên ~n~

Đầu ra

• Một số nguyên duy nhất: số lượng các ước nguyên tố của ~n~

Sample Input

12

Sample Output

2

Cho một số nguyên dương ~n~, đây là một số đặc biệt với mỗi chữ số đều mang một ý nghĩa riêng. Nhiệm vụ của bạn là tính tích của tất cả các chữ số trong số này. Đây có thể là chìa khóa để giải mã bí ẩn đằng sau những con số tưởng chừng như vô tri này.

Giới hạn

• ~1 ≤ n ≤ 10^{18}~

Đầu vào

• Dòng đầu tiên: số nguyên ~n~

Đầu ra

• Một số nguyên duy nhất: tích các chữ số của ~n~

Sample Input

12345

Sample Output

120

Bạn được cho một mảng gồm ~n~ phần tử phân biệt và có ~q~ truy vấn. Mỗi truy vấn bao gồm hai số nguyên, ~val~ và ~x~.

• Nếu ~x~ chưa tồn tại trong mảng, nhiệm vụ của bạn là chèn giá trị ~x~ vào ngay sau giá trị ~val~ trong mảng, với điều kiện ~x~ chưa tồn tại trong mảng.
• Nếu ~x~ đã tồn tại, bạn cần loại bỏ ~x~ khỏi vị trí cũ và sau đó chèn ~x~ vào ngay sau giá trị ~val~.
• Nếu ~val~ không tồn tại trong mảng thì chèn ~x~ vào đầu của mảng.

Input

• Dòng đầu tiên gồm hai số nguyên ~n, q~ ~(1 \le n,q \le 10^{5})~ và - đại diện cho số lượng phần tử trong mảng ban đầu và số lượng truy vấn trong mảng.
• Dòng thứ hai gồm ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 10^{18})~ - đại diện cho giá trị của phần tử thứ ~i~ trong mảng và các phần tử là phân biệt.
• ~q~ dòng tiếp theo chứa hai số nguyên ~x~, ~val~ ~(1 \le x,val \le 10^{18})~ - đại diện cho giá trị cần được chèn vào và giá trị cần chèn phía sau.

Output

• Dòng đầu tiên là kích thước của mảng sau khi đã được xử lí.
• Dòng thứ hai là các phần tử trong mảng.

Sample Input 1

5 3
2 1 4 7 10
1 3
3 4
3 7

Sample Output 1

6
1 2 4 7 3 10

Trong một xưởng làm bánh, ông chủ Godsent giao cho Nghialaptrinh một dãy n nguyên liệu, được đánh số từ 1 đến n.
Mỗi nguyên liệu a[i] thuộc về một loại bánh nhất định.

Ông chủ có k thùng chứa, được đánh số từ 1 đến k.

Ông chủ Godsent muốn Nghialaptrinh kiểm tra các phân đoạn nguyên liệu trên dây chuyền để làm ra những "gói bánh tuyệt vời".

Những gói bánh được tạo ra từ một phân đoạn nguyên liệu [l, r] sẽ được gọi là tuyệt vời nếu:

• Tất cả nguyên liệu trong đoạn con [l, r] được đưa vào thùng số 1.
• Tất cả các nguyên liệu còn lại (nằm ngoài đoạn con) có thể được phân chia tùy ý vào bất kỳ trong k thùng (bao gồm cả thùng số 1).
• Sau khi phân chia xong, cả k thùng đều chứa chính xác cùng một số lượng nguyên liệu của mỗi loại bánh.

Do quá kém trong việc lập trình, nên bạn hãy giúp Nghialaptrinh: Đếm số lượng đoạn con tuyệt vời nhé.

Input

• Dòng đầu tiên chứa số nguyên t (1 ≤ t ≤ 1000) - số lượng test case
• Dòng đầu tiên của mỗi test case chứa hai số nguyên n và k (1 ≤ n ≤ 2 * 10^5, 1 ≤ k ≤ n) — số lượng nguyên liệu và số lượng thùng.
• Dòng thứ hai chứa n số nguyên a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n) — Các loại nguyên liệu.

• Tổng tất cả các test case không vượt quá 2*10^5

  Output

• In ra một số nguyên duy nhất — số lượng đoạn con tuyệt vời.

Example

Input

4
3 2
1 1 1
4 2
1 2 1 2
8 2
3 3 3 3 2 2 2 2
6 3
1 1 1 1 1 1

Output

0
7
18
11

Giải thích test case:

test case 2: n = 4, a = [1, 2, 1, 2], k = 2

Tổng cộng có 2 nguyên liệu loại 1 và 2 nguyên liệu loại 2.

Muốn chia đều cho 2 thùng thì mỗi thùng phải có 1 nguyên liệu loại 1 và 1 nguyên liệu loại 2.

a[1->1] -> Thùng 1 chứa [1] -> còn lại [2,1,2]. Ta phân chia cho [2] vào thùng 1 -> [1,2] và đưa [1,2] còn lại vào thùng 2 -> [1,2]

-> Thùng 1 [1,2] = Thùng 2 [1,2] -> 1

a[2->2] -> Thùng 1 [2,1] = Thùng 2 [1,2] -> 2

a[3->3] -> Thùng 1 [1,2] = Thùng 2 [1,2] -> 3

a[4->4] -> Thùng 1 [2,1] = Thùng 2 [1,2] -> 4

a[1->2] -> Thùng 1 [1,2] = Thùng 2 [1,2] -> 5

a[2->3] -> Thùng 1 [2,1] = Thùng 2 [1,2] -> 6

a[3->4] -> Thùng 1 [1,2] = Thùng 2 [1,2] -> 7 -> answer

a[1->3] -> Thùng 1 [1,2,1] ≠ Thùng 2 [2]

Problem Statement

A function ~f(x)~ defined for non-negative integers ~x~ satisfies the following conditions.

• ~f(0) = 1~ .
• ~f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor)~ for any positive integer ~k~ .

Here, ~\lfloor A \rfloor~ denotes the value of ~A~ rounded down to an integer.

Find ~f(N)~ .

Constraints

• ~N~ is an integer satisfying ~0 \le N \le 10^{18}~ .

Input

The input is given from Standard Input in the following format:

~N~

Output

Print the answer.

Sample Input 1

2

Sample Output 1

3

We have ~f(2) = f(\lfloor \frac{2}{2}\rfloor) + f(\lfloor \frac{2}{3}\rfloor) = f(1) + f(0) =(f(\lfloor \frac{1}{2}\rfloor) + f(\lfloor \frac{1}{3}\rfloor)) + f(0) =(f(0)+f(0)) + f(0)= 3~ .

Sample Input 2

0

Sample Output 2

1

Sample Input 3

100

Sample Output 3

55