Bạn được nhận ~k \le 7~ chữ số ngẫu nhiên.

Yêu cầu: Dùng các chữ số bạn nhận được, hãy đếm xem có thể tạo ra được bao nhiêu số nguyên tố khác nhau.

Input

• Dòng đầu tiên là số ~T \le 10~ - số lượng test.
• ~T~ dòng tiếp theo, mỗi dòng gồm ~k~ chữ số tương ứng với một yêu cầu.

Output

• ~T~ dòng là kết quả của các test tương ứng theo thứ tự.

Sample Input 1

2
17
9999999

Sample Output 1

3
0

Giải thích

• Với ~2~ chữ số ~1,7~, tạo ra được 3 số nguyên tố là ~7, 17, 71~.
• Với ~7~ chữ số ~9~, không tạo ra được số nguyên tố nào.

Một xâu ~S~ được gọi là xâu đối xứng nếu ~S = S'~ với ~S'~ là xâu nhận được từ xâu ~S~ khi đọc từ phải qua trái. Ví dụ: Xâu ~'aba'~ là xâu đối xứng, còn xâu ~'abc'~ là xâu không đối xứng.

Cho một xâu ~S~ gồm ~1 \le n \le 1000~ kí tự.

Yêu cầu: Hãy tìm cách chia xâu ~S~ thành ít nhất các đoạn mà mỗi đoạn đều là các xâu đối xứng.

Input

• Dòng đầu gồm một số nguyên ~n~ là độ dài của xâu ~S~.
• Dòng thứ hai là nội dung xâu ~S~.

Output

• Dòng đầu ghi một số nguyên ~k~ (số đoạn ít nhất tìm được).
• ~K~ dòng sau, mỗi dòng ghi một số nguyên ~t_i~, với ~t_i~ là vị trí kết thúc của đoạn thứ ~i~.

Sample Input 1

 8
 abbacdcb

Sample Output 1

3
4
7
8

Người ta đo độ giống nhau của hai xâu ~X~, ~Y~ có độ dài bằng nhau là số vị trí mà hai kí tự tương ứng trên hai xâu giống nhau, tức là số chỉ số ~i~ thỏa mãn ~X_i = Y_i~. Ví dụ: ~X = 'avbc'~; ~Y = 'avvv'~ có độ giống nhau bằng ~2~. Cho một xâu ~S~ có độ dài ~n~ và một xâu ~T~ có độ dài ~m (m \le n)~, độ giống nhau giữa xâu ~S~ và xâu ~T~ là tổng số độ giống nhau giữa xâu ~T~ và mọi xâu con gồm các kí tự liên tiếp của ~S~ có độ dài ~m~.

Yêu cầu: Cho hai xâu ~S~ và ~T~. Tính độ giống nhau giữa xâu ~S~ và xâu ~T~.

Input

• Dòng đầu ghi xâu ~T~.
• Dòng thứ ~2~ ghi xâu ~S~.
• Các kí tự trong hai xâu thuộc ~'a' .. 'z'~ và có độ dài không quá ~2.10^6~ kí tự.

Output

• Gồm một số nguyên duy nhất là độ giống nhau giữa xâu ~S~ và xâu ~T~.

Subtask

• Có ~25\%~ số test ứng với ~0 < n ≤ 10^2~
• Có ~25\%~ số test ứng với ~10^2 < n ≤ 10^4~
• Có ~50\%~ số test ứng với ~10^4 < n ≤ 2.10^6~

Sample Input 1

 abaab 
 aababacab

Sample Output 1

12

Gần đây một trò chơi mới được du nhập vào Gensokyo, đó là chơi bài. Hôm nay Cirno cùng với Daiyousei sẽ thử chơi trò chơi mới này.

Bộ bài gồm có ~n~ lá bài được đặt trên bàn theo thứ tự từ trái sang phải, trên mỗi lá bài là một số nguyên, giá trị của lá bài. Cirno sẽ chọn một đoạn các lá bài từ ~l~ đến ~r~, sau đó Daiyousei sẽ chọn lá bài thứ ~j~ sao cho ~l \le j \le r~ và loại bỏ nó. Điểm nhận được là tổng các lá bài còn lại trong đoạn từ ~l~ đến ~r~.

Cirno muốn số điểm là lớn nhất có thể, còn Daiyousei lại muốn số điểm là nhỏ nhất có thể. Các bạn hãy giúp Cirno tìm cách chọn tối ưu để số điểm là lớn nhất nhé!

Input:

• Dòng đầu gồm số tự nhiên ~n~ là số lá bài.
• Dòng tiếp theo gồm ~n~ số nguyên ~a_i~ với ~1 \le i \le n~ là giá trị các lá bài.

Output:

• Một số nguyên điểm lớn nhất có thể.

Sample Test

Input 1:

5
5 -2 10 -1 4

Output 1:

6

Input 2:

3
-10 6 -15

Output 2:

0

Giới hạn:

• Trong tất cả các test: ~n \le 10 ^ 5, -10^9 \le a_i \le 10^9~.
• Subtask 1 (40%): ~n \le 1000~.
• Subtask 2 (30%): ~-30 \le a_i \le 30~.
• Subtask 3 (30%): Không có giới hạn gì thêm.

Phát minh mới nhất của của Nitori là một chiếc máy bay ném bom điều khiển từ xa. Ba nàng tiên ánh sáng đã đặt một chiếc cho kế hoạch khủng bố đền Hakurei.

Dĩ nhiên để máy bay có thể hoạt động thì cần có pin. Mỗi cục pin có 3 thông tin: ~e_i, w_i, c_i~ lần lượt và mức năng lượng, khối lượng và giá thành. Thời gian bay của máy bay được xác định bằng công thức: ~E\over{W}~ trong đó ~E~ là tổng mức năng lượng và ~W~ là tổng khối lượng của tất cả pin và khối lượng của máy bay.

Để đảm bảo kế hoạch thành công, máy bay cần hoạt động lâu nhất có thể. Ba nàng tiên có ngân sách ~b~ và khối lượng của máy bay là ~w~, hãy giúp họ chọn pin sao cho thời gian bay là lâu nhất!

Input:

• Dòng đầu chứa số ~n,b,w (1≤n×b≤10^5,1≤w≤1000)~.

• ~n~ dòng tiếp theo mỗi dòng chứa ba số ~e_i,w_i,c_i (0≤e_i,w_i≤1000,0≤c_i≤b)~ là mức năng lượng, khối lượng và giá thành của cục pin thứ ~i~.

Output:

• In ra tổng thời gian bay của máy bay, sai số không quá ~10^{-3}~.

Sample Test:

Input:

10 1000 20
40 40 40
1 1 1
70 30 60
100 20 700
80 50 200
30 1 200
100 100 1
20 1 500
30 20 100
70 50 100

Output:

3.1707

Giới hạn

• 25% số điểm ~n≤20~.
• 25% số điểm ~w_i=0~.
• 25% số điểm ~c_1=c_2=...=c_n~.
• 25% số điểm không có ràng buộc gì thêm.

Nhà máy sữa CodeMilk có ~N~ đại lý được xây dựng trên một con đường thẳng. Có thể mô tả con đường là một trục tọa độ, nhà máy sữa nằm tại vị trí gốc tọa độ, ~N~ đại lý ở tại các vị trí có tọa độ ~x_1,x_2,…,x_N~ ~(0 <x_1<x_2<⋯<x_N < 10^9)~, đại lý thứ ~i~ ~(i = 1,2,3,...,N)~ có vị trí tại tọa độ ~x_i~. Nhà máy có M chiếc xe dùng để vận chuyển sữa. Chiếc xe thứ ~i~, chuyển sữa từ đại lý ~s_i~ đến đại lý ~f_i~ ~(1 ≤s_i<f_i≤N)~, lượng xăng cần di chuyển cho ~1~ (đơn vị độ dài) là ~c_i~ (đơn vị thể tích) và số lần đổ xăng tối đa là ~r_i~, xe đi từ tọa độ ~x~ đến tọa độ ~y~ sẽ mất một lượng xăng ~|x-y|×c_i~. Các xe chỉ được di chuyển theo chiều dương của trục tọa độ và chỉ có thể đổ xăng khi đến vị trí của một đại lý nào đó. Xe không thể di chuyển nếu không còn xăng. Bình chứa xăng của ~M~ chiếc xe đều có dung tích giống nhau và bằng ~V~ (đơn vị thể tích). Khi bắt đầu xuất phát, bình xăng của tất cả các xe đã đầy xăng (không tính là một lần đổ xăng), mỗi lần đổ xăng, bình xăng được đổ đầy (tức là có ~V~ (đơn vị thể tích) xăng trong bình).</p>

Yêu cầu: Hãy tính xem, giá trị ~V~ nhỏ nhất bằng bao nhiêu để với mọi chiếc xe đều có thể vận chuyển được sữa, tức là chiếc xe thứ ~i~ có thể chuyển sữa được từ đại lý ~s_i~ đến đại lý ~f_i~ với mọi ~i=1,2,3,...,M~.

Input

• Dòng ~1~ ghi ~2~ số nguyên dương ~N~ và ~M~ tương ứng là số đại lý và số xe chở sữa.
• Dòng ~2~ ghi ~N~ số nguyên dương ~x_1,x_2,…,x_N~ ~(0<x_1<x_2<⋯<x_N<10^9)~ tương ứng là tọa độ của ~N~ đại lý.</li>
• ~M~ dòng cuối, dòng thứ ~i,(i=1,2,...,M)~ ghi ~4~ số nguyên ~s_i,f_i,c_i,r_i (1 ≤s_i<f_i≤N, 1 ≤c_i≤10^9;0≤r_i≤N)~ là thông tin của chiếc xe thứ i.</li>

Output

• Một số nguyên là giá trị nhỏ nhất của ~V~ để tất cả các xe đều có thể vận chuyển được sữa.

Subtask

• Có ~25\%~ số test ứng với ~1\le N \le 10^5, M = 1~.
• Có ~25\%~ số test ứng với ~2 \le N \le 100, 2 \le M \le 10~.
• ~50~ số test còn lại ứng với ~100 < N \le 400~, ~2 \le M \le 5.10^5~

Sample Input 1

5 2
1 3 8 12 15
1 3 10 0
2 4 5 1

Sample Output 1

70

Explanation 1

• Xe ~1~, di chuyển từ đại lý ~1~ đến đại lý ~3~, tức là tọa độ ~1~ đến tọa độ ~8~. Xe không được đổ xăng lần nào, do vậy sẽ dùng xăng trong bình lúc xuất phát. Lượng xăng ít nhất cần là ~|8-1|×10=70~ . Như vậy ~V~ bằng ~70~ thì xe ~1~ có thể đi được từ đại lý ~1~ đến đại lý ~3~.
• Xe ~2~, di chuyển từ đại lý ~2~ đến đại lý ~4~, tức là tọa độ ~3~ đến tọa độ ~12~. Xe được đổ xăng thêm một lần.
  • Đi từ tọa độ ~3~ đến tọa độ ~8~ hết ~|8-3|×5=25~.
  • Đi từ tọa độ ~8~ đến tọa độ ~12~ hết ~|12-8|×5=20~.
  • Như vậy, ~V = 25~ thì xe thứ ~2~ đi từ đại lý ~2~ đến đại lý ~3~; đổ xăng tại đại lý ~3~ và đi từ đại lý ~3~ đến đại lý ~4~.

• Do vậy, giá trị ~V~ nhỏ nhất để ~2~ xe có thể vận chuyển được sữa là ~70~.