Một số tự nhiên \(N\) có càng nhiều ước số tự nhiên thì càng đẹp, em hãy tính độ đẹp của một số tự nhiên \(N\) bất kì.

Input

• Gồm một dòng duy nhất ghi duy nhất một số tự nhiên \(𝑁\), biết \(𝑁 \leq 10^{14}\).

Output

• Gồm một dòng duy nhất là số ước của N.

Scoring

• Có 85% test chấm bài có \(1 \leq N < 10^8\);
• Có 15% test chấm bài có \(10^9 \leq 𝑁 \leq 10^{14}\).

Example

4

3

1234

4

Một số tự nhiên gọi là đối xứng khi viết các chữ số của nó theo chiều ngược lại thì ta vẫn thu được chính nó. Ví dụ như các số 66, 121 là số đối xứng.

Một số được coi là số đẹp nếu nó là số đối xứng và có từ 3 ước số nguyên tố khác nhau trở lên. Ví dụ: số 282 là số đẹp vì nó đối xứng và có 3 ước là số nguyên tố khác nhau là: 2, 3, 47. Hoặc số 858 cũng là số đẹp vì nó đối xứng và có 4 ước nguyên tố khác nhau là: 2, 3, 11, 13.

Cho hai số nguyên dương \(a, b\). Đưa ra số lượng số đẹp trong đoạn từ \(a\) đến \(b\).

Input

• Gồm một dòng duy nhất ghi hai số nguyên dương \(𝑎, 𝑏\) (\(1 < 𝑎 < 𝑏 ≤ 10^7\)).

Output

• Gồm một dòng duy nhất là số lượng số đẹp trong đoạn \(a\) đến \(b\).

Scoring

• Có 80% số test chấm có: \(1 \leq a, b \leq 10^4\);
• Có 20% test chấm bài có \(10^5 \leq a, b \leq 10^{7}\).

Example

1 1000 

25

Cho dãy số tự nhiên gồm N phần tử: \(𝑎_1, 𝑎_2, … 𝑎_𝑁\) và một số tự nhiên \(K\).

Đếm số lượng cặp chỉ số \((𝑖,𝑗)\) mà \(𝑖 < 𝑗\) và \(𝑎_𝑖 + 𝑎_𝑗 = 𝐾\) trong dãy.

Input

• Dòng đầu là hai số nguyên dương \(𝑁, K\) (\(2 \leq 𝑁 \leq 3.10^6, 1 \leq 𝐾 \leq 10^6\)).
• Dòng sau là dãy số: \(𝑎_1, 𝑎_2, … 𝑎_𝑁\) các số đều không quá \(10^6\).

Output

• Gồm một dòng duy nhất là số lượng cặp \(𝑎_𝑖, 𝑎_𝑗\) có tổng bằng \(K\).

Scoring

• Có 80% số test chấm có: \(1 \leq N \leq 10^3\);
• Có 20% test chấm bài có \(10^3 \leq a, b \leq 3.10^{6}\).

Example

5 1
1 5 4 1 2

0

4 6
3 2 3 3

3

Cho một xâu kí tự \(X\) gồm các chữ cái in thường từ ‘a’ đến ‘z’. Độ dài của xâu \(X\)
không quá \(10^6\). Người ta mã hóa xâu \(X\) thành xâu \(Y\) theo cách như sau:

Ban đầu xâu \(Y\) rỗng.

Đưa một kí tự trong xâu \(X\) vào cuối của xâu \(Y\) và lập tức đảo ngược xâu \(Y\). Các kí
tự của xâu \(X\) cứ đưa lần lượt như thế vào xâu \(Y\).

Em hãy in ra xâu \(Y\) cuối cùng nhận được khi đã đưa hết các kí tự của xâu \(X\) vào.

Input

• Gồm một dòng duy nhất là xâu \(X\).

Output

• Gồm một dòng duy nhất là xâu \(Y\).

Scoring

• Có 55% test chấm bài có độ dài xâu X không quá \(255\);
• Có 20% test chấm bài có độ dài xâu X không quá \(10^4\);
• Có 25% test chấm bài có độ dài xâu X không quá \(10^6\).

Example

abc

cab

Cho dãy gồm 𝑁 số tự nhiên: \(𝑎_1, 𝑎_2, … 𝑎_𝑁\).Người ta gọi một đoạn gồm các phần tử liên tiếp bất kì trong dãy ban đầu là đoạn con. Hai đoạn con là khác nhau nếu tồn tại ít nhất một phần tử không thuộc vào cả hai đoạn. Ví dụ dãy: {\(𝑎_1; 𝑎_2; 𝑎_3; 𝑎_4\)} thì có mười đoạn con là: {\(𝑎_1\)},{\(𝑎_2\)},{\(𝑎_3\)},{\(𝑎_4\)},{\(𝑎_1; 𝑎_2\)},{\(𝑎_2; 𝑎_3\)},{\(𝑎_3; 𝑎_4\)},{\(𝑎_1; 𝑎_2; 𝑎_3\)},{\(𝑎_2; 𝑎_3; 𝑎_4\)},{\(𝑎_1; 𝑎_2; 𝑎_3; 𝑎_4\)}.

Hãy đếm số đoạn con mà có tổng các lũy thừa bậc \(𝑀\) của các phần tử của đoạn đó chia hết cho \(𝐾\).

Input

• Dòng đầu ghi 3 số tự nhiên \(𝑁, 𝑀,𝐾\) tương ứng là số phần tử của dãy ban đầu, số mũ, và số \(K\) cần chia hết. (\(1 \leq 𝑁 \leq 10^5; 1 \leq 𝑀 \leq 10^{18}; 1 \leq 𝐾 \leq 10^5\)).

• Dòng tiếp theo ghi \(N\) số tự nhiên \(𝑎_1, 𝑎_2, … 𝑎_𝑁\) (các số đều không vượt quá \(10^{50}\),hay là: \(0 \leq 𝑎_𝑖 \leq 10^{50}\) với mọi \(i\) ).

Output

• Gồm một dòng duy nhất là số đoạn con mà có tổng các lũy thừa bậc \(M\) của các phần tử chia hết cho \(K\).

Scoring

• Có 45% test chấm bài có \(𝑀 = 1, 𝑁 ≤ 10^3, 𝑎_𝑖 \leq 10^6\);
• Có 30% test chấm bài có \(𝑀 \leq 1000, 𝑁 ≤ 10^5, 𝑎_𝑖 \leq 10^9\);
• Có 25% test chấm bài có \(10^9 \leq 𝑀 \leq 10^{18}, 𝑁 ≤ 10^5, 10^{30} \leq 𝑎_𝑖 \leq 10^9\);

Example

4 1 3
3 2 1 5

4

4 2 3
3 2 1 5

3