Ngày xưa có hai người chị em nọ, HienJeony là chị, em là AP. Cả năm qua để thưởng cho thành tích học tập của cả hai nên bố mẹ quyết định mua cho hai chị em ~n~ món đồ chơi, nhận thấy không ai nhường ai thế nên bố mẹ quyết rằng sẽ chia cho đồ chơi theo quy tắc hiệu của tổng giá tiền đồ chơi HienJeony được mua và tổng giá tiền đồ chơi AP được mua phải là một số nguyên tố lớn nhất có thể. Hãy xác định số nguyên tố này !

Input

• Dòng đầu tiên là ~n~ số đồ chơi mà bố mẹ mua cho cả hai chị em ~(1 \leq n \leq 20)~
• Dòng thứ hai gồm ~n~ số ~c_i~ là giá tiền của món đồ chơi thứ ~i~ ~(1 \leq c_i \leq 10^5)~

Output

• Một dòng duy nhất là số nguyên tố lớn nhất thỏa mãn yêu cầu, trong trường hợp không tồn tại số nguyên tố thỏa mãn thì in ra ~-1~

Sample Input

5
2 3 4 5 6

Sample Output

2

Subtask

• ~50\%~ số test có ~1 \leq n \leq 10~, ~1 \leq c_i \leq 10^4~.
• ~50\%~ số test có ~1 \leq n \leq 20~, ~1 \leq c_i \leq 10^5~

Dưới mái trường, hình ảnh cây bàng, cây phượng đã quá quen thuộc với nhiều thế hệ học sinh, nhưng đối với học sinh chuyên Tin như iostream1308 thì quen thuộc nhất vẫn là cây nhị phân. Tuy rằng iostream1308 không thích thú mấy với việc đếm lá cây bàng, cây phượng nhưng lại rất thích đếm lá cây của cây nhị phân, nhận thấy khả năng trời phú này, thầy giáo đã giao cho iostream một bài tập như sau:

Cho biết số lượng lá và độ cao của các lá trong một cây (coi độ cao của node gốc là ~0~). Hãy xác định ít nhất ~1~ cách tạo nên cây nhị phân đầy đủ. Biết rằng cây nhị phân đầy đủ là cây trong đó mỗi node (không phải node lá) đều có hai node con.

input:

• Dòng đầu tiên chứa số nguyên ~Q~ ~(1 \leq Q \leq 10)~ là số lượng truy vấn.
• ~Q~ dòng tiếp theo mỗi dòng chứa số nguyên dương ~n~ ~(1 \leq n \leq 10^5)~ là số lượng lá của cây và ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(1 \leq a_i \leq 10^5)~ là độ cao của ~n~ lá.

output:

• Ứng với mỗi truy vấn in ra kết quả của truy vấn đó trên một dòng. Nếu có thể tạo được cây nhị phân đầy đủ thì in ra ~YES~, ngược lại in ra ~NO~.

Sample Input:

3
4 2 2 2 2
3 1 2 2
2 1 2

Sample Output

YES
YES
NO

Subtask:

• ~20\%~ số test có ~1 \leq n \leq 4~.
• ~80\%~ số test còn lại không có điền kiện gì thêm.

Note

Ở test ví dụ thứ nhất ta được ~2~ cây sau đây:

Ta thấy rằng ở ~2~ cây này có tồn tại ít nhất ~1~ cây nhị phân đầy đủ nên đáp án là ~YES~

Bạn H giấu tên đang giải một bài tập hình thầy giao vô cùng khó như sau: Cho hình ngũ giác đều ~ABCDE~ nội tiếp đường tròn bán kính ~r~, từ ~AE~ và ~CD~ kéo dài cắt nhau tại ~K~, từ ~CE~ kéo dài ra để được ~EH~ bằng độ dài là ~x~. Bạn H tự hỏi rằng nếu như số ~r~ và ~x~ được thay đổi liên tục thì diện tích các phần tô màu sẽ là bao nhiêu, hãy giúp bạn H giấu tên tính diện tích phần được tô đậm !

Input

• Dòng đàu tiên gồm số nguyên ~T~ ~(1 \leq T \leq 10^5)~ là số câu hỏi.
• ~T~ dòng tiếp theo, mỗi dòng gồm số nguyên ~r~ và ~x~ ~(1 \leq r, x \leq 10^6)~

Output

• Gồm ~T~ dòng, mỗi dòng chứa một số là diện tích được tô đậm, biết rằng đáp án chỉ chấp nhận sai số chính xác là ~10^{-9}~

Sample Input

1
11 7

Sample Output

398.37063

Sau khi xem bộ phim "Queen's Gambit", Copium tập tành chơi cờ vua nhưng khổ nỗi không ai muốn chơi cờ với Copium cả, vì vậy Copium thường tự chơi với bàn cờ ~8 \times 8~ của mình. Trên bàn cờ của Copium có ~8~ quân xe và được xếp sao cho mỗi cột có đúng ~1~ quân xe, tuy vậy bàn cờ ban đầu không đàm bảo các quân xe không ăn nhau thế nên Copium cần xếp lại bàn cờ của mình để đảm bảo không quân xe nào ăn được nhau ( ~2~ quân xe có thể ăn nhau nếu thuộc cùng hàng hoặc cùng cột ). Ở mỗi thao tác, Copium được chọn một quân xe đang đứng ở ô ~(i,j)~ bất kì và di chuyển nó theo ~1~ trong ~2~ cách sau:

• Lùi lại ~k~ bước, mỗi bước đi từ ô ~(i, j)~ đang đứng đến ô ~(i-1, j)~ nếu ~i > 1~ hoặc ô ~(8, j)~ nếu ~i = 1~.
• Tiến lên ~k~ bước, mỗi bước đi từ ô ~(i, j)~ đang đứng đến ô ~(i+1, j)~ nếu ~i < 8~ hoặc ô ~(1, j)~ nếu ~i = 8~.

Giỏi chơi cờ là thế nhưng về những khoản tính toán như này Copium hơi kém, thế nên Copium đã soạn trước ~Q~ câu hỏi, ứng với mỗi câu hỏi Copium cho bạn biết được trạng thái của bàn cờ và số ~k~, vì vậy Copium cần biết số thao tác ít nhất để xếp lại bàn cờ sao cho thỏa mãn yêu cầu.

Input

• Dòng đầu tiên là số ~Q~ ~( 1 \leq Q \leq 10^6 )~ thể hiện cho số câu hỏi của Copium và số ~k~ ~(1 \leq k \leq 10^9)~
• Dòng thứ hai gồm ~Q~ chuỗi ~8~ chữ số, mỗi chữ số có giá trị từ ~1~ đến ~8~ đại diện cho vị trí các quân xe ở ~8~ cột

Output

• In ra ~Q~ dòng tiếp theo, mỗi dòng là số thao tác ít nhất cần di chuyển các quân xe sao cho thỏa mãn yêu cầu, in ra ~-1~ nếu không có cách xếp thỏa mãn.

Sample Input

3 2
12345672 17234568 11111111

Sample Output

1 
0
-1

Sample Input

2 1
11111111 12121212

Sample Output

16
12

Subtask

• ~30\%~ số test có ~1 \leq Q \leq 10~.
• ~20\%~ số test có ~ k = 1 ~.
• ~50\%~ số test còn lại không có ràng buộc gì thêm.

Note

Sau buổi học về số nguyên tố, Muối cảm thấy rất phấn khích khi được biết đến số nguyên tố, nếu có ai hỏi Muối một số nguyên tố thì ngay lập tức Muối có thể trả lời ngay số nguyên tố liền trước và số nguyên tố liền sau. Muối cảm thấy vô địch trong lĩnh vực số nguyên tố nhưng ngày vui ngắn chẳng tày gang, thầy giáo liền cho Muối ~n~ số ~a_i~ và bắt Muối đếm số cách tạo số nguyên tố đặc biệt. Biết rằng số nguyên tố đặc biệt chính là số nguyên tố được tạo nên từ tổng phép XOR tập con bất kì trong những số ~a_i~ thầy giáo cho và tập con đó có ít nhất là ~1~ phần tử. Cảm thấy sự vô địch của mình bị đe dọa, bạn hãy giúp Muối trả lời những câu hỏi của thầy nhé !

Lưu ý: ~2~ cách được gọi là khác nhau khi ~2~ tập con tạo nên số nguyên tố đặc biệt sau khi sắp xếp lại là khác nhau.

Input

• Dòng đầu tiên gồm số ~Q~ ~(1 \leq Q \leq 10)~ là số câu hỏi mà thầy giáo sẽ đặt ra cho Muối
• Ở câu hỏi thứ ~T~ ~(1 \leq T \leq Q)~, dòng thứ nhất cho số ~n~ ~(1 \leq n \leq 10^5)~, dòng thứ hai cho ~n~ số ~a_i~ ~(1 \leq a_i \leq 5000)~

Lưu ý: gọi ~M~ là số lớn nhất trong ~n~ số ~a_i~, ~m~ là số nhỏ nhất trong ~n~ số ~a_i~ thì dữ liệu luôn đảm bảo ~M-m \leq 1000~

Output

• Ứng với ~Q~ câu hỏi, mỗi câu hỏi cho biết số cách tạo số nguyên tố đặc biệt theo định nghĩa của thầy giáo, vì số cách tạo số nguyên tố đặc biệt có thể rất lớn nên đáp án được lấy chia dư cho ~10^9+7~

Sample Input

1
5
3515 3511 3510 3512 3520

Sample Output

5

Sample Input

2
2
3 3
3
3 3 3

Sample Output

1
2

Subtask

• ~50\%~ số test có ~1 \leq n \leq 1000~, ~1 \leq a_i \leq 5000~
• ~50\%~ số test tiếp theo có ~1 \leq n \leq 100000~, ~1 \leq a_i \leq 5000~

Note

Với ~ \oplus ~ là phép XOR đã được đề cập, ta có:

~3511~ là số nguyên tố

~3515 \oplus 3520 \oplus 3510 = 3533~ là số nguyên tố

~3512 \oplus 3515 = 3~ là số nguyên tố

~3515 \oplus 3510 = 13~ là số nguyên tố

~3515 \oplus 3511 \oplus 3510 \oplus 3512 = 2~ là số nguyên tố

~\rightarrow~ Có tổng ~5~ cách tạo nên số nguyên tố đặc biệt

Tình hình bệnh dịch đang diễn biến phức tạp ở đất nước Bedao, vì vậy chính phủ đã họp bàn để đưa ra kế hoạch tuyên truyển về cách phòng chống bệnh dịch trên khắp đất nước. Bản đồ đất nước Bedao gồm ~n~ địa điểm và ~n-1~ con đường. Mỗi con đường có đơn vị độ dài là ~1~. Chủ tịch thành phố cử ~1~ người ở thành phố ~A~ và ~1~ người ở thành phố ~B~ đi tuyên truyền. Biết rằng ~2~ người này sẽ đi thông qua các con đường để tuyên truyền với ràng buộc như sau:

• ~2~ người xuất phát cùng lúc và đi liên tục với tốc độ bằng nhau
• Không đi đến địa điểm cũng như con đường mà ~1~ trong ~2~ người đã đi qua .
• Mọi lúc trong cuộc tuyên truyền ~2~ người phải ở ~2~ địa điểm khác nhau (~2~ người không cùng đến ~1~ chỗ)
• Chiến dịch tuyên truyền chỉ dừng khi ~1~ trong ~2~ người không thể di chuyển được nữa.

Tìm phương án di chuyển sao cho số lượng địa điểm mà mỗi người đến gồm cả điểm bắt đầu là lớn nhất.

Input

• Gồm ~1~ dòng chứa số nguyên ~n~ ~(1 \leq n \leq 2 \times 10^5)~ là số địa điểm trong đất nước cần phải đến
• ~n-1~ dòng tiếp theo gồm ~2~ đỉnh ~u~ và ~v~ biểu thị con đường nối giữa địa điểm ~u~ và địa điểm ~v~ ~(1 \leq u,v \leq n)~
• Dòng thứ ~n~ gồm ~2~ số nguyên ~A~ và ~B~ lần lượt là địa điểm xuất phát của cả ~2~ người ~(1 \leq A,B \leq n, A \neq B)~

Output

• Một dòng duy nhất là số lượng địa điểm tối ưu mà mỗi người đến được.

Sample Input

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

Sample Output

2

Subtask

• ~50\%~ số test có ~1 \leq n \leq 1000~
• ~50\%~ số test còn lại không có điều kiện gì thêm