New Season Contest div 2

Cho \(n\). Các bạn hãy tính \(n!\).

Hẳn các bạn đã gặp bài toán này rất nhiều lần rồi. ami muốn nâng cấp bài toán này lên tầm bài cuối div 1 codeforces, và sau đây là thành quả.

Cho một số \(X\). Hãy đếm xem có bao nhiêu số nguyên không âm \(n\) mà \(n! = X\).

Input

• Dòng đầu tiên chứa \(t\) là số câu hỏi.

• Mỗi câu hỏi là một số nguyên dương \(X\).

Output

• Với mỗi câu hỏi, hãy in ra số các số \(n\) mà \(n! = X\).

Constants

• Trong tất cả các test có \(1 \leq X \leq 10^{18}\).

Example

3
2
3
6 

1
0
1

ami có một xâu kí tự \(S\) gồm các chữ cái tiếng anh thông thường \((a ... z)\). Các bạn cần thêm vào một vài kí tự để xâu này thành xâu đối xứng. Cảm thấy bài này quá đơn giản vì chỉ cần đảo ngược xâu \(S\) và gắn với chính nó là được, ami liền biến nó thành bài khó bằng cách giới hạn số kí tự cần thêm.

Cụ thể, các bạn chỉ được phép thêm tối đa \(1\) kí tự vào cuối xâu \(S\) để biến xâu \(S\) thành xâu đối xứng. Hãy thông báo cho ami biết có cách thêm nào như vậy hay không.

Xâu đối xứng là xâu mà đọc từ trái sang hay phải sang đều giống nhau. Ví dụ \(aba\) là xâu đối xứng còn \(cuomgavl\) thì không phải.

Input

• Dòng đầu tiên chứa 1 số nguyên \(t\) là số bài toán bạn phải giải.

• \(t\) dòng tiếp theo, mỗi dòng chứa một xâu \(S\).

Output

• In ra \(t\) dòng tương ứng với \(t\) xâu. Ứng với mỗi xâu, in ra "YES" nếu bạn có thể biến nó thành xâu đối xứng, "NO" nếu không thể.

Constrains

• \(t \leq 10\).
• Độ dài mỗi xâu không vượt quá \(10^5\).

Example

2
lqdoj
a 

NO
YES

• Cho một mảng gồm \(N\) phần tử và số nguyên \(K(0\le K<N)\).

• Nhiệm vụ của chúng ta là xóa đi \(K\) phần tử từ mảng \(A\) sao cho số lượng phần tử còn lại khác nhau là nhiều nhất và in ra giá trị lớn nhất đó

Input

• Dòng thứ nhất chứa số nguyên \(T\) - thể hiện số lượng testcase (\(1\le T\le 100\))

• \(T\) block tiếp theo ,mỗi block có dạng như sau:

• Dòng thứ nhất chứa số nguyên \(N(0<N\le 10000)\)

• Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,...,a_N(1\le a_i\le N)\)

• Dòng thứ ba chứa số nguyên \(K(0\le K<N)\)

Output

• Ứng với mỗi block, in ra đáp án cần tìm.

Scoring

• \(20\%:0<N\le 10\)

• \(40\%:11\le N\le 100\)

• \(40\%: 101\le N\le 10^4\)

Example

1
3
1 1 2
1

2

In ra tất cả cặp số nguyên tố \(A,B(A\le B)\) thỏa mãn \(A+B\) cũng là số nguyên tố và \(A+B\le N\). (In theo thứ tự từ điển từ bé đến lớn)

Input

• Dòng thứ nhất chứa số nguyên dương \(N(1\le N\le 10^6)\)

Output

• Dòng thứ nhất in ra số \(k\) - số lượng cặp \((A,B)\) thỏa mãn yêu cầu bài toán

• In ra \(k\) cặp \((A,B)\) thỏa mãn yêu cầu bài toán (theo thứ tự từ điển từ bé đến lớn).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(0<N\le 10\)

• Subtask \(2\) (\(20\%\) số điểm): \(0<N\le 10^4\)

• Subtask \(3\) (\(60\%\) số điểm): \(\text{Còn lại}\)

Example

7

2
2 3
2 5

Cho điểm \(C\) có tọa độ \((x,y)\) trên mặt phẳng \(Oxy\).

Một đường thẳng bất kì đi qua \(C\) cắt trục \(Ox,Oy\) lần lượt tại \(A\) và \(B\) sao cho \(C\) nằm giữa \(A,B\).

Tìm giá trị nhỏ nhất của tích \(P=|CA| * |CB|\)

(Trong đó: \(|CA|,|CB|\) lần lượt là độ dài các đoạn \(CA,CB\))

Input

• Một thứ nhất chứa số nguyên \(T(1\le T\le 500)\) - Thể hiện số testcase

• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x,y(0<x,y\le 10000)\) - Thể hiện tọa độ điểm \(C\)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm.(Sai số không quá \(10^{-6}\))

Scoring

• Subtask \(1\) (\(40\%\) số điểm): x=y

• Subtask \(2\) (\(60\%\) số điểm): không có điều kiện gì thêm

Example

1
1 1

2.000000000

• Nhân ngày đẹp trời, bố của \(Henry\) đố \(Henry\) một bài toán như sau:

• Cho \(2\) số nguyên dương \(n\) và \(m\). Hỏi có bao nhiêu số có \(n\) chữ số thỏa mãn tổng các chữ số của nó bằng \(m\).

Sau một đêm ngẫm nghĩ và nghiên cứu, \(Henry\) nhận ra rằng: bài này không thể đếm theo kiểu tay chân được, nên quyết định lên đây để nhờ các bạn. Là một lập trình viên tài năng, các bạn hãy giúp anh ấy một tay nhé!

Input

• Một dòng duy nhất chứa hai số nguyên \(n,m(1\le n\le 100,1\le m\le 900)\).

Output

• In ra đáp án cần tìm. Vì đáp số rất lớn, các bạn chỉ cần in ra số dư của đáp án sau khi chia \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(0<n\le 6\).

• Subtask \(2\) (\(20\%\) số điểm): \(0<m\le 3\).

• Subtask \(3\) (\(60\%\) số điểm): không có điều kiện gì thêm.

Example

2 3

3

Cho điểm \(C\) có tọa độ \((x,y)\) trên mặt phẳng \(Oxy\).

Một đường thẳng bất kì đi qua \(C\) cắt trục \(Ox,Oy\) lần lượt tại \(A\) và \(B\) sao cho \(C\) nằm giữa \(A,B\)

Tìm giá trị nhỏ nhất của \(P=p * |CA|+q*|CB|\).

(Trong đó: \(|CA|,|CB|\) lần lượt là độ dài các đoạn \(CA,CB\) và \(p,q\) là các số nguyên dương cho trước )

Input

• Một thứ nhất chứa số nguyên \(T(1\le T\le 500)\) - Thể hiện số testcase

• \(T\) dòng tiếp theo, mỗi dòng chứa \(4\) số nguyên \(x,y,p,q(0<x,y,p,q\le 10000)\).

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm. (Sai số không quá \(10^{-6}\))

Scoring

• Subtask \(1\) (\(40\%\) số điểm): x = y

• Subtask \(2\) (\(60\%\) số điểm): còn lại

Example

1
1 1 1 1

2.828427125