Lõi dữ liệu của một hệ thống máy tính được bảo vệ bởi một con số N. Chìa khóa để giải mã hệ thống này chính là ước số lớn nhất của N mà ước số đó phải là một số chính phương (số có căn bậc hai là một số nguyên). Hãy viết chương trình tìm ra chìa khóa này.

Input: Một số nguyên dương N (1 <= N <= 10^12).

Output: Ước số chính phương lớn nhất của N.

Ví dụ:

Input:

18

Output:

9

(Giải thích: Các ước của 18 là 1, 2, 3, 6, 9, 18. Trong đó 1 và 9 là số chính phương. Số lớn nhất là 9).

Một đoạn mã liên lạc được gọi là "nhị nguyên" nếu nó chỉ chứa tối đa 2 loại ký tự khác nhau. Cho một xâu ký tự S, hãy tìm độ dài của xâu con liên tiếp nhị nguyên dài nhất nằm trong S.

Input: Một xâu S chỉ gồm chữ cái in thường (Độ dài <= 10^5).

Output: Độ dài của xâu con liên tiếp thỏa mãn.

Ví dụ:

Input:

eceba

Output:

3

(Giải thích: Xâu con "ece" có độ dài 3 và chỉ chứa 2 loại ký tự là 'e' và 'c').

Tại trường Đại học Cảnh sát nhân dân, ban chỉ huy giao cho một tiểu đội đi tuần tra N khu vực. Khu vực thứ i đòi hỏi Ti giờ để tuần tra xong và có thời hạn chót là Di giờ (tính từ thời điểm 0). Nếu khu vực i hoàn thành lúc Ci mà Ci > Di, tiểu đội sẽ bị ghi nhận độ trễ là Ci - Di (nếu Ci <= D_i thì độ trễ là 0). Hãy sắp xếp thứ tự tuần tra các khu vực sao cho "độ trễ lớn nhất" trong số N khu vực là nhỏ nhất có thể.

Input:

Dòng 1: N (1 <= N <= 10^5).

N dòng tiếp theo: Mỗi dòng 2 số nguyên Ti, Di (1 <= Ti, Di <= 10^9).

Output: Độ trễ lớn nhất nhỏ nhất có thể đạt được.

Ví dụ:

Input:

3
2 5
3 3
1 10

Output:

0

(Giải thích: Thứ tự tuần tra: khu vực 2 (mất 3h, xong lúc 3h, hạn 3h -> trễ 0). Khu vực 1 (mất 2h, xong lúc 5h, hạn 5h -> trễ 0). Khu vực 3 (mất 1h, xong lúc 6h, hạn 10h -> trễ 0). Độ trễ lớn nhất là 0.

Bạn được cung cấp một chuỗi s bao gồm n chữ cái viết thường, n là chẵn. Đối với mỗi vị trí i (1≤i≤n) trong chuỗi s, bạn được yêu cầu thay đổi chữ cái trên vị trí này thành chữ cái đứng trước theo thứ tự chữ cái hoặc sang vị trí tiếp theo (chữ 'a' và 'z' chỉ có một những lựa chọn này). Mọi vị trí trong chuỗi phải được thay đổi chính xác một lần. Ví dụ: có thể thay đổi chữ 'p' thành 'o' hoặc thành 'q', chữ 'a' nên được đổi thành 'b' và chữ 'z' được đổi thành 'y' mà không thể đổi thành 'a'. Ví dụ, chuỗi "codeforces" có thể được thay đổi thành "dpedepqbft" ('c' → 'd', 'o' → 'p', 'd' → 'e', 'e' → 'd', 'f' → 'e', 'o' → 'p', 'r' → 'q', 'c' → 'b', 'e' → 'f', 's' → 't'). Chuỗi s được gọi là palindrom nếu nó đọc tương tự từ trái sang phải và từ phải sang trái. Ví dụ: chuỗi "abba" và "zz" là palindromes và chuỗi "abca" và "zy" thì không. Mục tiêu của bạn là kiểm tra xem có thể biến chuỗi s thành một chuỗi palindrome hay không bằng cách áp dụng các thay đổi đã nói ở trên cho mọi vị trí. In "YES" nếu chuỗi s có thể được chuyển thành bảng màu và "NO" nếu không. Mỗi testcase chứa một số chuỗi, đối với mỗi chuỗi, bạn được yêu cầu giải quyết vấn đề một cách riêng biệt.

Đầu vào:

• Dòng đầu tiên chứa một số nguyên T (1≤T≤50) - số testcase.
• Sau đó, các dòng 2T theo sau . Dòng đầu tiên của testcase chứa một số nguyên n (2≤n≤100, n là chẵn) - độ dài của chuỗi tương ứng. Dòng thứ hai của testcase chứa một chuỗi s, bao gồm n chữ cái Latinh viết thường.

Đầu ra: In dòng T. Dòng thứ i nên chứa câu trả lời cho chuỗi thứ i của đầu vào. In "YES" nếu có thể biến chuỗi thứ i thành chuỗi palindrome bằng cách áp dụng các thay đổi đã nói ở trên cho mọi vị trí. In "NO" nếu không.

Input:

5
6
abccba
2
cf
4
adfa
8
abaazaba
2
ml

Output:

YES
NO
YES
NO
NO