Nauw có một dãy ~a~ gồm ~n~ phần tử phân biệt: ~a_1, a_2, a_3, \ldots, a_n~.

Tìm tổng ~a_i+a_j+a_k~ lớn nhất sao cho:

• ~1 \le i < j < k \le n~.

• ~a_i < a_j < a_k~.

Nếu như không tồn tại ~i, j, k~ thỏa mãn thì in ra ~-1~. Hãy giúp Nauw giải quyết bài toán này nhé!

Input

• Dòng đầu tiên ghi một số nguyên ~n~ là số phần tử của dãy ~a~ (~3 \le n \le 5000~).

• Dòng thứ hai ghi ~n~ số nguyên dương phân biệt mô tả dãy ~a~ (~1\le a_i \le 10^5~).

Output

• In ra một số nguyên dương duy nhất là kết quả của bài hoặc in ra ~-1~ nếu như không có đáp án.

Scoring

Subtask	Điểm	Giới hạn
1	~30~	~3\le n \le 300~
2	~70~	Không có ràng buộc gì thêm

Sample Input 1

7
1 5 2 3 4 9 6

Sample Output 1

16

Notes

Giá trị tốt nhất đạt được khi ~i=4, j=5, k=6~, và tổng là ~a_i + a_j + a_k = 3 + 4 + 9 = 16~.

Nauw là một người rất thích chơi game nên anh quyết định tổ chức một giải đấu LOL cho ~n~ người chơi với luật như sau:

Gọi ~a_i~ là số điểm của người ~i~ ở thời điểm lượt chơi cần xét. Ban đầu ~a_i = 0~ với mọi ~i~.

Thực hiện liên tục các lượt chơi cho đến khi trò chơi dừng lại, mỗi lượt sẽ diễn ra như sau:

• Chọn ra ~2~ đối thủ ~x~ và ~y~ để đấu với nhau, sao cho ~|a_x - a_y| \le 1~. Nếu không tồn tại ~2~ đối thủ như vậy, trò chơi sẽ được dừng lại.

• Người thua sẽ bị loại và số người chơi giảm xuống ~1~.

• Gọi người thắng là ~x~, thì tăng ~a_x~ lên ~1~: ~a_x = a_x + 1~.

Hỏi với một giải đấu gồm ~n~ người tham gia, xét mọi cách sắp xếp trận đấu có thể xảy ra, số điểm lớn nhất mà một người có thể đạt được trước khi bị loại hoặc sau khi trò chơi dừng là bao nhiêu?

Nauw có ~q~ câu hỏi như trên cần phải được trả lời. Do còn bận đi chuẩn bị cho giải đấu nên bạn hãy giúp Nauw trả lời giúp ~q~ câu hỏi đó.

Input

• Dòng đầu chứa số nguyên dương ~q~ (~1\le q \le 10^6~) thể hiện số lượng test.

• ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~ (~1\le n \le 10^{18}~).

Output

• ~q~ dòng, mỗi dòng in ra một số nguyên dương duy nhất là kết quả của test tương ứng.

Sample Input 1

2
4
7

Sample Output 1

2
3

Notes

Ở ví dụ ~1~, số điểm lớn nhất có thể đạt được là ~2~ bằng cách sau:

• Cặp (~1, 2~) đấu với nhau, người ~1~ thắng.

• Cặp (~3, 4~) đấu với nhau, người ~3~ thắng.

• Cặp (~1, 3~) đấu với nhau, người ~1~ thắng.

Ở ví dụ ~2~, số điểm lớn nhất có thể đạt được là ~3~ bằng cách sau:

• Cặp (~1, 2~) đấu với nhau, người ~1~ thắng.

• Cặp (~1, 3~) đấu với nhau, người ~1~ thắng.

• Cặp (~4, 5~) đấu với nhau, người ~4~ thắng.

• Cặp (~6, 7~) đấu với nhau, người ~6~ thắng.

• Cặp (~4, 6~) đấu với nhau, người ~4~ thắng.

• Cặp (~1, 4~) đấu với nhau, người ~1~ thắng.

Hãy tìm dãy số ~p_1, p_2, \dots, p_n~ dài nhất sao cho:

• ~p_i~ (~1 \leq i \leq n~) là số nguyên tố trong khoảng ~[1, 10^7]~.

• ~p_i \neq p_j~ với ~i \neq j~ (~1 \leq i, j \leq n~).

• Trung bình cộng của ~p~ ~\left(\frac{p_1 + p_2 + \dots + p_n}{n}\right)~ là số nguyên tố.

Input

Bài không có input.

Output

Dòng đầu tiên in ra số ~n~. (~1 \leq n \leq 10^7~)

Dòng thứ hai in ra dãy số ~p_1, p_2, \dots, p_n~ thỏa mãn. (~1 \leq p_i \leq 10^7~)

Scoring

Giới hạn	Điểm
~1 \leq n \leq 100~	~\frac{n}{10}~
~100~ ~\text{<}~ ~n \leq 1000~	~10 + 2 \cdot \frac{n - 100}{90}~
~1000~ ~\text{<}~ ~n \leq 50000~	~30 + 2 \cdot \frac{n - 1000}{4900}~
~50000~ ~\text{<}~ ~n \leq 400000~	~50 + 2 \cdot \frac{n - 50000}{35000}~
~400000~ ~\text{<}~ ~n \leq 600000~	~70 + 3 \cdot \frac{n - 400000}{20000}~
~600000~ ~\text{<}~ ~n~	~100~

Sample Input 1

Sample Output 1

10
7 11 13 17 19 23 29 31 37 43

Notes

Dãy ~p~ ở ví dụ thỏa mãn tất cả các điều kiện đề bài; để ý rằng trung bình cộng của dãy — ~\frac{7+11+13+17+19+23+29+31+37+43}{10} = 23~ là số nguyên tố.

Ví dụ này sẽ nhận được ~\frac{10}{10} = 1~ điểm.

Cho dãy số ~a~ độ dài ~n~.

Đếm số cặp ~(i, j)~ (~i \neq j~, ~1 \leq i, j \leq n~) sao cho tổng OR của ~a_i~ và ~a_j~ bằng tổng OR của ~n - 2~ số còn lại.

Hai cặp ~(i_1, j_1)~ và ~(i_2, j_2)~ được coi là khác nhau khi ~i_1 \neq i_2~ hoặc ~j_1 \neq j_2~.

Bạn có thể tìm hiểu về phép toán OR ở đây.

Input

Dòng đầu tiên là số nguyên ~n~ (~3 \leq n \leq 10^6~) là độ dài dãy ~a~.

Dòng tiếp theo gồm n số nguyên ~a_1, a_2, ..., a_n~ (~1 \leq a_i < 2^{20}~).

Output

In ra số lượng cặp ~(i, j)~ thỏa mãn.

Scoring

Subtask	Điểm	Giới hạn
~1~	~20\%~	~n \leq 500~
~2~	~20\%~	~n \leq 10^4~
~3~	~60\%~	Không có ràng buộc gì thêm

Sample Input 1

6
1 2 3 10 9 8

Sample Output 1

12

Notes

Có 12 cặp ~(i, j)~ thỏa mãn là:

~(1, 4)~, ~(4, 1)~, ~(2, 5)~, ~(5, 2)~, ~(3, 4)~, ~(4, 3)~, ~(3, 5)~, ~(5, 3)~, ~(3, 6)~, ~(6, 3)~, ~(4, 5)~, ~(5, 4)~.

Xét cặp ~(1, 4)~:

— ~a_1~ OR ~a_4~ = ~1~ OR ~10~ = ~11~.

— ~a_2~ OR ~a_3~ OR ~a_5~ OR ~a_6~ = ~2~ OR ~3~ OR ~9~ OR ~8~ = ~11~.

Vì tổng OR của ~a_1~ và ~a_4~ bằng tổng OR của các số còn lại nên cặp ~(1, 4)~ là một cặp thỏa mãn.

Cho một số nguyên dương ~n~, hãy đếm số cặp ~(x, y)~ mà:

• ~1 \le x \le y \le n~.

• ~\gcd(x, n)\times\gcd(y, n)=\gcd(x\times y, n)~.

Với hàm ~\gcd(x, y)~ là ước chung lớn nhất của ~x, y~.

Input

• Dòng đầu chứa số nguyên dương ~T~ (~1\le T \le 10^5~) thể hiện số lượng test.

• ~T~ dòng tiếp theo mỗi dòng chứa một số nguyên dương ~n~ (~1\le n \le 10^5~).

Output

• ~T~ dòng mỗi dòng in ra một số nguyên dương duy nhất là kết quả của test tương ứng.

Scoring

Subtask	Điểm	Giới hạn
1	~30~	~1\le T \le 50, 1\le n \le 500~
2	~70~	Không có ràng buộc gì thêm

Sample Input 1

2
3
4

Sample Output 1

5
8

Notes

• Ở test ví dụ thứ 1: có các cặp ~(x,y)~ thỏa mãn là: ~(1,1),(1,2),(1,3),(2,2),(2,3)~.

• Ở test ví dụ thứ 2: có các cặp ~(x,y)~ thỏa mãn là: ~(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(3,3),(3,4)~.

Nauw có một cây gồm ~n~ đỉnh và ~n-1~ cạnh. Độ đẹp ~h(u, v)~ của một cặp điểm ~u, v~ là số lượng các trọng số cạnh xuất hiện nhiều hơn ~1~ lần trong đường đi từ ~u \rightarrow v~.

Cụ thể, ta gọi các trọng số cạnh trên đường đi từ ~u \rightarrow v~ là ~w_1, w_2, w_3, ..., w_k~ thì ~h(u, v)= \sum_{i=1}^{k} (p(w_i)>1)~, với ~p(w_i)~ là số lần xuất hiện của ~w_i~ trong mảng ~w~.

Độ đẹp của cả cây sẽ bằng tổng của tất cả các ~h(u, v)~ với mọi ~u, v~ (~1 \le u < v \le n~). Hãy tính độ đẹp của cây.

Input

• Dòng đầu chứa số nguyên dương ~n~ (~3\le n \le 10^5~) thể hiện số lượng đỉnh.

• ~n-1~ dòng tiếp theo mỗi dòng chứa ba số nguyên dương ~u, v, w~ (~1\le u \neq v \le n, w \le n~) thể hiện một cạnh của cây.

Output

• In ra một số nguyên dương duy nhất là kết quả của bài.

Scoring

Subtask	Điểm	Giới hạn
1	~20~	~3\le n \le 300~
2	~30~	Cạnh thứ ~i~ nối đỉnh ~i~ và đỉnh ~i+1~.
3	~50~	Không có ràng buộc gì thêm

Sample Input 1

3
1 2 3
3 2 3

Sample Output 1

2

Sample Input 2

4
1 4 2
4 2 2
3 4 1

Sample Output 2

2

Notes

Ở test ví dụ thứ ~1~:

Chỉ có ~h(1, 3)=2~, còn lại tất cả các cặp khác đều là ~0~.

~\Rightarrow~ Đáp án là ~2~.

Ở test ví dụ thứ ~2~:

Chỉ có ~h(1, 2)=2~, còn lại tất cả các cặp khác đều là ~0~.

~\Rightarrow~ Đáp án là ~2~.