Bạn Phong đang học đến phần ước số của một số nguyên dương trong môn Toán, vì tò mò nên bạn muốn biết số nguyên dương ~N~ có bao nhiêu ước số. Phong nghe nói môn Tin học lập trình giải quyết vấn đề này rất dễ dàng. Em hãy giúp Phong thực hiện công việc đó.

Input

Dữ liệu vào gồm một số nguyên dương ~N~ ~(1 \le N \le 10^9)~.

Output

Dữ liệu ra gồm một số duy nhất là số lượng ước số của số nguyên dương ~N~.

Sample Input 1

8

Sample Output 1

4

Notes

Số ~8~ có ~4~ ước là ~1~, ~2~, ~4~, ~8~

Cho xâu kí tự ~S~ chỉ bao gồm các ký tự chữ cái Latin in thường và ký tự chữ số. Viết chương trình đếm số lượng ký tự chữ số trong xâu ~S~.

Input

Gồm 1 dòng duy nhất chứa xâu ký tự ~S~. Độ dài xâu ~S~ không vượt quá ~250~ ký tự.

Output

Gồm một số nguyên duy nhất là số lượng ký tự chữ số trong xâu ~S~.

Sample Input 1

aba812abc

Sample Output 1

3

Notes

Có ~3~ ký tự chữ số là ~8~, ~1~, ~2~.

Cho một dãy gồm ~n~ số nguyên ~a_1,a_2,...,a_n~ và ~m~ câu hỏi dạng ~u,v~ ~(1 \le u \le v \le n)~. Với mỗi câu hỏi có dạng trên, hãy kiểm tra xem tổng các số nguyên ~a_u + a_{u+1} + \ldots + a_v~ có phải số nguyên tố hay không?

Input

Dòng đầu tiên chứa hai số nguyên dương ~n,m~ là số phần tử trong dãy và số câu hỏi.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(|a_i| \le 10^4)~.

~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~u,v~ tương ứng là câu hỏi thứ ~i~ yêu cầu kiểm tra tổng các số nguyên ~a_u + a_{u+1} + \ldots + a_v~ có phải số nguyên tố hay không?

Output

In ra ~m~ dòng, dòng thứ ~i~ ~(1 \le i \le m)~ tương ứng với kết quả của câu hỏi ~i~, ghi số ~1~ nếu là tổng các số nguyên tố, ngược lại ghi số ~0~.

Scoring

Sample Input 1

5 3
2 7 3 4 6
3 4
3 5
2 4

Sample Output 1

1
1
0

Notes

~a_3 + a_4 = 3+4 = 7;~

~a_3 + a_4 + a_5 = 3 + 4 + 6 = 13;~

~a_2 + a_3 + a_4 = 7 + 3 + 4 = 14.~

Cho dãy gồm ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~. Hãy kiểm tra xem trong dãy số đã cho có hay không cặp ~(u, v)~ ~(1 \leq u, v \leq N)~ thoả mãn:

• ~a_u~ là số chẵn

• ~a_v~ là số lẻ.

• ~a_u + a_v = k~.

Input

Dòng đầu tiên chứa số nguyên dương ~t~ ~(2 \leq t \leq 5)~ là số bộ test, mỗi bộ test được mô tả trên ~2~ dòng:

• Dòng thứ nhất chứa hai số nguyên dương ~(N, k)~.

• Dòng thứ hai chứa ~N~ số nguyên dương ~a_i~ ~(1 \leq i \leq N)~.

Output

Ghi ra ~t~ ký tự, ký tự thứ ~i~ là ~1~ nếu bộ test thứ ~i~ có cặp ~(u, v)~ thỏa mãn điều kiện đề bài, ngược lại ghi ~0~.

Scoring

Sample Input 1

2
4 6
3 2 4 3
9 13
11 7 1 5 3 2 4 6 9

Sample Output 1

01

Notes

• Test 1: Không có cặp ~(u, v)~ nào thỏa mãn điều kiện đề bài.

• Test 2 : Có nhiều cặp ~(u, v)~ thỏa mãn như cặp ~u = 6; v = 1~ có ~a_u+a_v=13~.