Bài tập

Bạn được cho 2 số nguyên dương \(a\) và \(b\).

Viết chương trình tìm số thứ \(n\) chia hết cho \(a\) hoặc \(b\).

Input

• Dòng đâu tiên chứa số nguyên dương \(T\) \((T \leq 10^5)\) - là số câu hỏi.

• \(T\) dòng, mỗi dòng chứa 3 số nguyên dương \(a, b, n\) \((a,b \leq 10^4, N \leq 10^9)\).

Output

• Gồm \(T\) dòng, mỗi dòng chứa câu trả lời cho mỗi câu hỏi.

Example

1
2 3 10

15

Nhân dịp năm mới An quyết định mua tặng hai người bạn thân của mình mỗi người một món quà. Trong cửa hàng lưu niệm có \(N\) mặt hàng khác nhau, mặt hàng thứ \(i\) có giá \(a_{i}\), \(i=1,2,…,N\). Với số tiền mang theo là \(X\), An quyết định sẽ mua hai món quà khác nhau có tổng giá trị lớn nhất nhưng không vượt quá số tiền đang có.

Yêu cầu: Bạn hãy xác định xem số tiền mà An cần chi trả để mua quà là bao nhiêu?

Input

Dữ liệu vào từ tệp văn bản BAI3.INP:

--- Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(X\) \((2≤ N ≤ 10^5,2 ≤ X ≤ 10^9)\)

--- Dòng thứ hai chứa \(N\) số nguyên dương \(a_1,a_2,…,a_N\) (\(1 ≤ a_{i} ≤ 10^9,i=1,2,…,N)\). Các số cách nhau \(1\) dấu cách.

Output

Kết quả ghi ra tệp văn bản BAI3.INP một số nguyên dương là số tiền mà An cần chi trả.

Example

6 18
5 3 10 2 4 9

15

Cho một danh sách \(n\) số nguyên dương, nhiệm vụ của bạn là đếm số cặp số nguyên mà nguyên tố cùng nhau (tức là, ước số chung lớn nhất của chúng là một).

Input

• Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng phần tử.

• Dòng tiếp theo có \(n\) số nguyên \(x_1, x_2, ... ,x_n\): nội dung của danh sách.

Output

• In một số nguyên: câu trả lời cho nhiệm vụ.

Example

8
5 4 20 1 16 17 5 15

19

Bài tập của An hôm nay là bài tập về xâu ký tự và tính đối xứng của xâu. Một xâu ký tự được gọi là đối xứng nếu đọc các ký tự của nó từ trái sang phải cũng như đọc từ phải sang trái.

Ví dụ: \(a, aa, aba, abba\) là các xâu đối xứng, xâu \(babaa\) không phải là xâu đối xứng.

Yêu cầu: Cho một xâu gồm các chữ cái Latin in thường, không đối xứng. Hãy thêm vào bên trái xâu đó một số chữ cái để thu được một xâu đối xứng và cho biết độ dài xâu ngắn nhất tạo được là bao nhiêu?

Input

Dữ liệu vào từ tệp văn bản BAI4.INP gồm một dòng chứa xâu đã cho, có độ dài không quá \(500000\) chữ cái Latin in thường.

Output

Kết quả ghi ra tệp văn bản BAI4.OUT một số nguyên dương là độ dài của xâu đối xứng ngắn nhất tạo được.

Example

babaa

7

Scoring

Có \(60\%\) số test tương ứng với \(60\%\) số điểm có \(N \leq 200000\).

\(40\%\) còn lại không có ràng buộc gì thêm.