Số nguyên dương ~p~ được gọi là chia hết cho số nguyên dương ~q~ nếu tồn tại một số nguyên dương ~n~ sao cho ~p = n \times q~. Trường hợp ~p~ không chia hết cho ~q~ thì luôn tồn tại số nguyên không âm ~x~ thỏa mãn ~(p + x)~ chia hết cho ~q~.

Yêu cầu: Cho ~2~ số nguyên ~a, b~ (~1 \le a, b \le 10^9~). Tìm số nguyên không âm ~c~ nhỏ nhất sao cho ~(a + c)~ chia hết cho ~b~ và ~(b + c)~ chia hết cho ~a~.

Input

Dữ liệu vào gồm một dòng chứa ~2~ số nguyên dương ~a, b~.

Output

Kết quả ghi ra một số nguyên ~c~ nhỏ nhất thỏa yêu cầu.

Sample Input 1

8 1

Sample Output 1

7

Sample Input 2

10 10

Sample Output 2

0

Dũng là một nhà sưu tập vòng đá có thâm niên. Những chiếc vòng được kết từ nhiều viên đá, mỗi viên đá có một màu sắc khác nhau và thứ tự các viên đá tạo nên một độ thẩm mĩ nhất định.

Bên cạnh đó, Dũng cũng yêu thích số học nên đưa ra một định nghĩa hơi riêng biệt về độ thẩm mĩ. Dũng mã hóa màu sắc của các viên đá thành một số nguyên có giá trị từ ~1~ đến ~10^6~. Theo Dũng, độ thẩm mĩ của vòng đá là số lượng lớn nhất các viên đá xét theo thứ tự được kết (có thể không được kết liên tiếp nhau) tạo thành một dãy thỏa các điều kiện sau:

• Các viên đá trong dãy này có mã màu là các số nguyên có cùng số ước.
• ~2~ viên đá kề nhau trong dãy này phải khác màu nhau.

Chẳng hạn vòng đá có các màu ~8, 4, 25, 10, 6, 6, 9, 15~ có độ thẩm mĩ là ~4~.

Yêu cầu: Cho ~r~ các vòng đá khác nhau. Hãy giúp Dũng tìm vòng đá có độ thẩm mĩ cao nhất.

Input

• Dòng đầu tiên chứa số nguyên ~r~ (~1 \le r \le 50~) – số lượng các vòng đá cần thẩm định.
• Mỗi vòng đá được mô tả trên ~2~ dòng: dòng đầu chứa số nguyên ~n~ (~1 \le n \le 10^3~) là số lượng viên đá, dòng tiếp theo chứa ~n~ số nguyên là mã các viên đá được kết theo thứ tự tương ứng.

Output

Kết quả ghi ra một số nguyên là độ thẩm mĩ cao nhất của ~r~ vòng đá.

Sample Input 1

3
8
8 4 25 10 6 6 9 15
5
13 18 1 12 20
7
21 8 5 26 12 34 35

Sample Output 1

5

Tetris là một trò chơi điện tử đã từng rất phổ biến tại Việt Nam. Trò chơi gồm ~5~ khối cơ bản (khối I, khối O, khối T, khối S và khối L), mỗi khối được tạo từ ~4~ ô vuông đơn vị. Các khối có thể xoay theo chiều kim đồng hồ để tạo thành các dạng khác nhau.

Mỗi khối có một màu riêng biệt biểu diễn bằng các kí tự chữ cái in thường từ 'a' đến 'z', các ô vuông thuộc cùng một khối có cùng màu nhau. Xét một trạng thái của bảng game kích thước ~n \times m~ gồm các khối được lắp vào bảng sao cho ~2~ ô vuông chung cạnh nhau nếu không thuộc cùng một khối thì có màu khác nhau, những ô trống biểu diễn bởi kí tự '#'.

Yêu cầu: Cho bảng trạng thái trò chơi kích thước ~n \times m~, gồm các kí tự chữ cái in thường từ 'a' đến 'z' biểu diễn màu và kí tự '#' biểu diễn ô trống. Hãy đếm số lượng khối mỗi loại.

Input

• Dòng đầu tiên chứa ~2~ số nguyên ~n, m~ (~1 \le n, m \le 1000~) – kích thước bảng trò chơi.
• ~n~ dòng tiếp theo, mỗi dòng chứa chuỗi độ dài ~m~ gồm các kí tự chữ cái in thường và kí tự '#'.
• Dữ liệu đảm bảo ~2~ ô vuông thuộc cùng một khối có cùng màu, ~2~ ô vuông chung cạnh không thuộc cùng một khối có màu khác nhau.

Output

Kết quả ghi ra ~5~ số nguyên – tương ứng số lượng khối I, khối O, khối T, khối S và khối L.

Sample Input 1

5 6
aaabba
aobbaa
#ocdda
#ocdd#
#occ##

Sample Output 1

1 1 1 1 2

Cho ~2~ số nguyên ~n~ và ~k~. Tìm số nguyên ~m~ lớn nhất thỏa mãn các điều kiện sau:

• ~m \le n~
• Trong phân tích thừa số nguyên tố của ~m~ có đúng ba số nguyên tố liên tiếp. Cụ thể, ~m = p_1^{t_1} \times p_2^{t_2} \times p_3^{t_3}~, với ~p_1, p_2, p_3~ là ba số nguyên tố liên tiếp và ~t_1, t_2, t_3 \ge 1~.
• Số lượng các ước của ~m~ đúng bằng ~k~.

Yêu cầu: Hãy tìm số nguyên ~m~ thỏa mãn yêu cầu đề bài. Dữ liệu vào đảm bảo luôn tồn tại kết quả.

Input

Dữ liệu vào gồm một dòng chứa hai số nguyên ~n~ và ~k~ (~1 \le n \le 10^{18}, 8 \le k \le 2700~).

Output

Kết quả ghi ra một số nguyên ~m~ là kết quả của bài toán.

Sample Input 1

32 8

Sample Output 1

30

Sample Input 2

110 8

Sample Output 2

105