Với mọi số nguyên dương x ta luôn biến đổi được ~\sqrt{x}~ và thành tích a. ~\sqrt{b}~ với a, b là các số nguyên dương. Việc biến đổi như vậy gọi là đưa thừa số ra ngoài dấu căn.

Yêu cầu: Cho trước số nguyên dương x (x ≤ 10~^{14}~). Hỏi trong các cách biến đổi ~\sqrt{x}~ Và thành tích a. ~\sqrt{b}~ (với a, b là các số nguyên dương) thì số a lớn nhất là số nào?

Ví dụ: Với x = 72 ta có ~\sqrt{x} = \sqrt{72} = 1.\sqrt{72} = 2.\sqrt{18} = 3.\sqrt{8} = 6.\sqrt{2}~. Khi đó số a lớn nhất là 6.

Dữ liệu vào: Đọc ở file văn bản CBH.INP một số nguyên dương x (x ≤ 10~^{14}~).

Dữ liệu ra: Ghi ra file văn bản CBH.OUT số a lớn nhất cần tìm. Ví dụ:

CBH.INP

72

CBH.OUT

6

CBH.INP

10

CBH.OUT

1

You are given an array of ~n~ positive integers. Your task is to find two integers such that their greatest common divisor is as large as possible.

Input

• The first input line has an integer ~n~: the size of the array.~(2 \le n \le 2 * 10^5)~,
• The second line has ~n~ integers ~x_1, x_2, ..., x_n~: the contents of the array ~(1 \le x_i \le 10^6)~.

Output

• Print the maximum greatest common divisor.

Scoring

• Không giới hạn gì thêm

Ví dụ

Input

5
3 14 15 7 9

Output

7

Một xâu kí tự được gọi là xâu đối xứng nếu ta đọc xâu này từ trái sang phải hoặc từ phải sang trái là như nhau. Chẳng hạn xâu 'abcba' là một xâu đối xứng.

Yêu cầu

Cho trước một xâu kí tự S không chứa kí tự trống (dấu cách). Hãy tìm cách cắt xâu S thành 2 xâu (2 xâu này phải khác xâu rỗng) là P và Q (với P là phần đầu, Q là phần còn lại của xâu S) sao cho khi ghép xâu P vào sau xâu Q ta được một xâu kí tự mới là xâu kí tự đối xứng.

Dữ liệu vào: Đọc ở file văn bản XKT.INP một xâu kí tự S (xâu S có không quá 255 kí tự)

Dữ liệu ra: Ghi ra file văn bản XKT.OUT một số nguyên k là độ dài của xâu P. Trường hợp không có cách cắt nào thỏa mãn yêu cầu đề bài thì ghi ra file văn bản XKT.OUT một số 0.

Chú ý: Trường hợp có nhiều cách cắt thỏa mãn yêu cầu đề bài thì chọn cách cắt sao cho độ dài của xâu P là nhỏ nhất.

Ví dụ

Sample input 1

cbaabcd

Sample output 1

3

Giải thích: Có S = 'cbaabcd' ta cắt thành 2 xâu P = 'cba'; Q = 'abcd'. Khi đó ghép xâu P vào sau xâu Q ta được xâu kí tự: 'abcdcba' là một xâu đối xứng.

Sample input 2

abaabaabaaba

Sample output 2

3

Trên một vòng tròn được đánh số từ 1 đến 10, một chú rô bốt đứng tại vị trí số 1. Rô bốt di chuyển trên vòng tròn theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ. Lệnh để rô bốt di chuyển là 1 số nguyên n.

Quy ước: Nếu số n là số nguyên dương, rô bốt sẽ đi chuyển theo chiều kim đồng hồ, nếu n là số nguyên âm, rô bốt sẽ di chuyển ngược chiều kim đồng hồ; nếu n = 0 rô bốt đứng yên

INPUT: Số nguyên n

OUTPUT: Vị trí đứng của rô bốt

Bạn được cấp 2 số nguyên dương n và k. In ra màn hình số nguyên dương thứ K mà không chia hết cho n.

Ví dụ: n=3 và k = 7, tất cả các số không chia hết cho 3 là 1, 2, 4, 5, 7, 8, 10, 11, 13,... Số thứ 7 là 10.

INPUT

Dòng đầu tiên chứa số nguyên t  (1≤t≤1000) là số trường hợp. 

T dòng tiếp theo, mỗi dòng chứa 2 số nguyên n (2 <= n <= 10⁹) và k (2 <= k <= 10⁹) 

OUTPUT

Mỗi dòng chứa số nguyên thứ K không chia hết cho n