Cho số nguyên dương \(N\) và mảng \(A\) đã được sắp xếp tăng dần. Cho số nguyên \(X\). Hãy đếm số lần \(X\) xuất hiện trong mảng \(A\).

Input

• Dòng đầu tiên đưa vào số lượng bộ test \(T\) (\(1 \leq T \leq 100\)).
• Dòng đầu mỗi bộ test nhập vào số nguyên \(N\) và \(X\) (\(1 \leq N \leq 10^3, 1 \leq X \leq 5000\)).
• Dòng thứ hai mỗi bộ test nhập \(N\) số nguyên \(A_i\) (\(1 \leq i \leq N, 1 \leq A_i \leq 5000\)).

Output

• In ra kết quả theo yêu cầu đề bài.

Example

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

3
0

Cho một mảng gồm \(n\) số nguyên dương \(a_{1}, a_{2}, a_{3},..., a_{n}\). Hỏi có bao nhiêu cặp số \(i < j\) và \(a_{i} = a_{j}\).

Lưu ý: Số lượng này có thể rất lớn nên sử dụng kiểu long long.

Input

• Dòng thứ nhất là chiều dài \(n\) của mảng \((1 \leq n \leq 10^{5})\)
• Dòng thứ hai gồm \(n\) số nguyên \(a_{1}, a_{2}, a_{3},..., a_{n}\) \((1 \leq a_{i} \leq 10^{5})\), mỗi số cách nhau một khoảng trắng.

Output

• Gồm 1 dòng duy nhất là số nguyên xác định số lượng các cặp bằng nhau.

Example

5
8 2 9 8 1  

1

7
6 2 4 2 4 3 4

4

Cho số nguyên dương \(N\), \(X\) và mảng \(A\) gồm \(N\) số nguyên. Hãy kiểm tra xem \(X\) có xuất hiện trong mảng \(A\) hay không? Nếu có thì in ra 1, còn ngược lại thì in ra 0.

Input

• Nhập số nguyên dương \(N\) và \(X\) (\(1 \leq N \leq 10^5, 1 \leq X \leq 5000\)).
• Nhập \(N\) số nguyên \(A_i\) (\(1 \leq i \leq N, 1 \leq A_i \leq 5000\)).

Output

• In ra kết quả theo yêu cầu đề bài.

Example

5 3
1 2 3 4 5

1

Cho mảng \(A\) gồm \(N\) số nguyên. Nhiệm vụ của bạn là sắp xếp mảng theo số lần xuất hiện các phần tử của mảng. Số xuất hiện nhiều lần nhất đứng trước. Nếu hai phần tử có số lần xuất hiện như nhau, số nhỏ hơn đứng trước. Ví dụ \(A = {5, 5, 4, 6, 4 }\), ta nhận được kết quả là \(A[] = {4, 4, 5, 5, 6}\).

Input

• Dòng đầu tiên đưa vào số lượng bộ test \(T\) (\(1 \leq T \leq 100\)).
• Những dòng kế tiếp đưa vào \(T\) bộ test. Mỗi bộ test gồm hai dòng:
  • Dòng đầu tiên đưa vào \(N\) (\(1 \leq N \leq 10^4\)), tương ứng với số phần tử của mảng \(A\);
  • Dòng tiếp theo là \(N\) số \(A_i\) (\(1 \leq i \leq N, 1 \leq A_i \leq 10^5\)); các số được viết cách nhau một vài khoảng trống.

Output

• Đưa ra kết quả mỗi test theo từng dòng.

Example

2
5
5 5 4 6 4
5
9 9 9 2 5

4 4 5 5 6 
9 9 9 2 5 

An muốn biết một số có phải là số nguyên tố không. Nếu số \(n\) là số nguyên tố, bạn hãy in ra "YES", nếu không hãy in ra ước nguyên tố dương nhỏ nhất của \(n\).

Input

• Gồm một dòng duy nhất chứa số nguyên dương \(n\) \((n \leq 10^6)\).

Output

• Gồm một dòng duy nhất chứa kết quả của bài toán.

Example

5

YES

6

2

Nguồn: Học sinh Giỏi THCS Hà Nội năm 2014 - 2015

Cho trước số nguyên dương \(t\). Người ta tạo một số nguyên dương \(x\) bằng cách sau: Trước hết, biểu diễn số \(t = p_1 \times p_2 \times p_k\), trong đó \(p_i\) (\(1 \leq i \leq k\)) là các số nguyên tố (\(k\) có thể bằng \(1\)); tiếp theo viết các số \(p_1, p_2, \dots, p_k\) theo một thứ tự nào đó liên tiếp nhau để nhận được số nguyên dương \(x\).

Yêu cầu: Tìm giá trị lớn nhất của \(x\).

Dữ liệu vào từ tệp văn bản CAU3.INP:

• Chứa số nguyên dương \(t\) không vượt quá \(10^9\).

Output

Kết quả ra tệp văn bản CAU3.OUT:

• Ghi ra giá trị \(x\) lớn nhất tìm được.

Examples

476

72217

Note

• Có \(476 = 2 \times 2 \times 7 \times 17\) nên số \(x\) lớn nhất là \(72217\).

Bé Bi đang dùng casio để tính toán, nhưng chiếc máy tính của Bi hình như đang hỏng. Hãy giúp bé tính toán \(N\) số, được liệt kê sẵn trên giấy. Với số ở vị trí lẻ tính từ đầu dãy, hãy thực hiện phép cộng. Còn nếu số đó ở vị trí chẵn, hãy thực hiện phép trừ.

Input

• Dòng đầu tiên ghi số \(n\) \((0 < n \leq 10000)\).
• Dòng thứ 2 ghi \(n\) số nguyên \(a_i\) \((|a_i| \leq 10^5)\).

Output

• Một dòng duy nhất in ra đáp án.

Example

3
1 2 3

2