Một số nguyên dương được gọi là số tròn nếu như tổng các chữ số (trong hệ thập phân) của nó là bội của ~10~.

Hãy tìm số tròn nhỏ thứ ~N~.

Input

Số nguyên dương ~N~ ~(N \le 10^5)~.

Output

In ra số tròn thứ ~N~.

Sample Input

1

Sample Output

19

Sample Input

10

Sample Output

109

~AP~ đố ~Hermione~ và bạn một bài toán như sau:

Cho ~2~ xâu ký tự ~s~ và ~t~, mỗi ký tự trong cả ~2~ xâu chỉ thuộc ~1~ trong ~2~ ký tự đặc biệt. ~2~ ký tự đặc biệt là ~2~ kí tự chữ cái in hoa bất kì được chọn. Hỏi cần tối thiểu bao nhiêu bước hoán đổi vị trí ~2~ kí tự liền kề trong xâu ~s~ để có thể chuyển thành xâu ~t~.

~Hermione~ tinh mắt nhận ra ~AP~ giấu tờ giấy đáp án ở sau lưng và cô ngay lập tức đọc thần chú "~Accio \ paper \ of \ solution~" (câu thần chú có thể nhìn xuyên thấu) và tìm ngay ra được lời giải. Còn bạn, một người không biết phép thuật chỉ trỏ bùm chíu như Hermione nhưng bạn lại biết "phép thuật" của thời hiện đại - lập trình. Bạn có thể giải được câu đố này không?

Input:

• Gồm hai chuỗi ~s~ và ~t~ với độ dài không quá ~10^5~.

Output:

• Gồm một số nguyên duy nhất là số bước tối thiểu để biến ~s~ thành ~t~.
• In ra ~-1~ nếu không thể biến chuỗi ~s~ thành chuỗi ~t~.

Sample Input

AABB
BAAB

Sample Output

2

Subtask:

• ~20\%~ số test có ~min(|s|, |t|) <= 10~.

• ~80\%~ số test không có ràng buộc gì thêm.

Hôm nay, bạn D lục lại trong kho code cũ của mình và thấy một đoạn mã giả viết về một hàm có nội dung như sau :

func f(array a[n])
     c = 0
     for i = 1 to n - 3
         for j = i + 1 to n - 2
             for x = j + 1 to n - 1
                 for y = x + 1 to n
                     if a[i] + a[j] + a[x] + a[y] = 0 : c = c + 1
     return c

Bạn D rất thích thú với hàm này nên muốn tăng tốc nó để có thể tìm ra kết quả trong ~1s~ với giới hạn đề bài cho. Các bạn hãy giúp D làm việc này nhé.

Input

• Dòng đầu tiên chứa số nguyên ~n~ là độ dài của dãy ~(n \le 2\times 10^3)~.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ ~(|a_i| \le 10^6)~.

Output

• In ra một số duy nhất là kết quả của hàm này.

Sample Input

5
1 2 -1 -3 0

Sample Output

1

Subtask

• ~30\%~ số test có ~n \le 10~
• ~20\%~ số test tiếp theo có ~n \le 300~
• ~50\%~ số test còn lại không có điều kiện gì thêm

Note

Có duy nhất ~1~ bộ là ~(1, 2, -3, 0)~

~Neko~ rất thích chơi bi, nhất là khi chơi cùng với bạn bè của mình.

Vào một ngày đẹp trời, ~Neko~ nhận ra nhiều viên bi của mình đã không cánh mà bay. Do mất quá nhiều bi nên ~Neko~ không còn hứng thú với việc giữ bi nữa, anh muốn chia đều bi cho tất cả bạn bè của mình.

Tuy nhiên số lượng bi có hạn mà bạn bè lại quá đông. Hiện giờ ~Neko~ đang có ~a~ viên bi đỏ và ~b~ viên bi xanh, anh ấy muốn biết mình có thể chia cho nhiều nhất bao nhiêu người sao cho mỗi người có ~x~ viên bi đỏ và ~y~ viên bi xanh hoặc ~x~ viên bi xanh và ~y~ viên bi đỏ. Bạn hãy giúp ~Neko~ nhé!

* Lưu ý: Neko là người rất hào phóng nên sẽ luôn luôn chia cho mỗi người một lượng bi là số nguyên dương (trong trường hợp chia được).

Input:

• Dòng đầu chứa số nguyên dương ~T~ là số bộ test. ~(T \leq 10^4)~

• ~T~ dòng sau mỗi dòng chứa ~4~ số nguyên không âm ~a,b,x,y~ là dữ liệu của từng bộ test. (~ a,b,x,y \leq 10^9~)

Output:

• Gồm ~T~ dòng, dòng thứ ~i~ là kết quả của bộ test thứ ~i~.

Sample Input

2
1 1 2 2
10 12 2 5

Sample Output

0
3

Subtask

• ~30\%~ số test có ~a, b, x, y \leq 20~.
• ~20\%~ số test tiếp theo có ~a, b, x, y \leq 1000~.
• ~50\%~ số test còn lại không có điều kiện gì thêm.

~iostream~ giao cho ~tahp~ viết content cho ~Bedao \ Regular \ 04~. Thế nhưng vốn từ quá ít ỏi cộng thêm tâm hồn khô khan khiến cho ~tahp~ không thể nào viết được một câu chuyện hay để hấp dẫn mọi người. Vì thế ~tahp~ quyết định viết đề bài một cách đơn giản như cách làm của bài này vậy. Đề bài như sau:

Cho mảng ~a~ gồm ~n~ số nguyên dương đánh số từ ~1~ đến ~n~, bạn phải trả lời các truy vấn sau :

Với mỗi truy vấn cho ~1~ cặp số ~L~, ~R~, hãy đếm số lượng giá trị nguyên ~x~ sao cho ~log_x(LCM(a[L..R]))~ là một số nguyên dương.

Chú ý : ~LCM(a[L..R])~ là bội chung nhỏ nhất của tất cả các phần tử trong mảng ~a[1..n]~ có chỉ số thuộc đoạn ~[L, R]~.

Tất nhiên vì bài trên quá đơn giản để làm E của regular 4 nên bạn cần trả lời truy vấn theo 1 cách khác:

• cho ~q~ nhóm truy vấn, mỗi nhóm được biểu thị bởi ~1~ cặp số ~k~, ~R~. Kết quả của một nhóm truy vấn là tổng kết quả của mọi truy vấn ~L~, ~R~ sao cho ~k \le L \le R~.

Ví dụ : kết quả của nhóm truy vấn ~[3, 5]~ ~(k = 3, R = 5)~ là tổng kết quả các truy vấn ~[3, 5]~, ~[4, 5]~ và ~[5, 5]~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~ ~(n \le 5 \times 10^5, q \le 10^5)~.

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(a_i \le 4 \times 10^6)~.

• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~k~, ~R~ thể hiện một nhóm truy vấn ~(1 \le k \le R \le n)~.

Output

• In ra ~q~ dòng, mỗi dòng là kết quả tương ứng của một nhóm truy vấn.

Sample Input

5 3
1 2 9 12 16
1 2
2 4
5 5

Sample Output

2
5
3

Subtask

• ~10\%~ số test có ~q = 1~, có duy nhất 1 nhóm truy vấn là ~[1, n]~
• ~30\%~ số test khác có ~a_i~ là một lũy thừa của ~2~ và mọi nhóm truy vấn đều có ~k~ = 1.
• ~60\%~ số test còn lại không có điều kiện gì thêm.

Dũng là một chú hề nổi tiếng trong rạp xiếc ~Bedao~. Gần đây cậu được giao nhiệm vụ chuẩn bị một vở hài kịch thật đặc biệt dành tặng khán giả.

Cậu có ~n~ quả bóng, quả bóng thứ ~i~ được viết số nguyên ~a_i~. Dũng muốn sơn các quả bóng này thành ~1~ trong ~2~ màu trắng hoặc đen để chuẩn bị cho buổi biểu diễn của mình.

Gọi ~W~ là tổng XOR của các số nguyên ở những quả bóng màu trắng. ~B~ là tổng XOR của các số nguyên ở những quả bóng màu đen.

Độ thú vị của ~n~ quả bóng này được tính bằng giá trị ~W + B~.

Dũng dành tất cả tâm huyết cho từng màn biểu diễn nên cậu muốn tối đa hóa độ thú vị của ~n~ quả bóng. Hãy giúp cậu ấy nhé!

Input

• Dòng đầu tiên chứa số nguyên ~n~ là số lượng quả bóng. ~(2 \le n \le 10^5)~
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ lần lượt là số ghi trên từng quả bóng. ~(0 \le a_i \le 2^{60})~

Output

• Gồm một số nguyên là độ thú vị lớn nhất có thể tìm được.

Sample Input

5
1 2 3 4 5

Sample Output

13

Subtask

• ~10\%~ số test có ~2 \le n \le 20~.
• ~30\%~ số test tiếp theo có ~2 \le n \le 400, 0 \le a_i \le 400~.
• ~60\%~ số test còn lại không có điều kiện gì thêm.