Cho một số nguyên dương ~A~.

Yêu cầu

Viết chương trình kiểm tra xem ~A~ có phải là diện tích của một tam giác vuông có các cạnh là số nguyên hay không. Nếu có in ra YES, nếu không in ra NO.

Dữ liệu đầu vào

Gồm ~T + 1~ dòng:

• Dòng đầu chứa số nguyên ~T~ ~(T \le 1000)~ là số lượng số ~A~ cần kiểm tra.
• ~T~ dòng tiếp theo, mỗi dòng ghi một số ~A~ ~(A \le 10^6)~.

Dữ liệu đầu ra

Gồm ~T~ dòng, mỗi dòng là một chữ YES hoặc NO tương ứng với dữ liệu đề bài.

Ràng buộc dữ liệu

• Có 20% số điểm thỏa mãn ~T = 2~ và ~A \le 100~;
• Có 30% số điểm thỏa mãn ~2 < T \le 100~ và ~A \le 100~;
• Có 50% số điểm không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

3
6
24
50

OUTPUT

YES
YES
NO

Giải thích:

• Với ~A = 6~ tam giác vuông thỏa mãn yêu cầu đề bài có các cạnh lần lượt là: ~3; 4; 5~.
• Với ~A = 24~ tam giác vuông thỏa mãn yêu cầu đề bài có các cạnh lần lượt là: ~6; 8; 10~.
• Với ~A = 50~ không có tam giác vuông nào thỏa mãn yêu cầu đề bài.

Cho một xâu ~S~ chỉ gồm các ký tự chữ cái trong bảng chữ cái tiếng Anh và các chữ số từ 0 đến 9. Một số trong xâu ~S~ được định nghĩa là một ký tự chữ số hoặc là các kí tự số liên tiếp và không bao gồm các chữ số 0 không có nghĩa.

Ví dụ với xâu ~S =~ 05aAb21b3956cDe488a, các số có trong xâu là: ~5; 21; 3956; 488~.

Yêu cầu

Cho xâu ~S~ chỉ gồm các kí tự chữ cái tiếng Anh và các chữ số. Hãy viết chương trình tìm số chính phương lớn nhất có trong xâu ~S~. (Số chính phương là số bằng bình phương của một số nguyên, ví dụ ~9~ là số chính phương vì ~9 = 3^2~).

Dữ liệu đầu vào

Gồm gồm xâu ~S~ chỉ chứa các ký tự chữ cái trong bảng chữ cái tiếng Anh và chữ số (dữ liệu đảm bảo xâu ~S~ có không quá ~18~ chữ số có nghĩa liền nhau và độ dài xâu không quá ~10^5~ ký tự).

Dữ liệu đầu ra

Gồm số chính phương lớn nhất tìm được hoặc số ~-1~ nếu không tìm được số chính phương nào.

Ràng buộc dữ liệu

• Có 30% số điểm thỏa mãn xâu ~S~ có độ dài không quá ~250~ ký tự;
• Có 30% số điểm thỏa mãn xâu ~S~ có độ dài không quá ~10^3~ ký tự;
• Có 40% số điểm không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

aBc2144gHf81Dgf09gf

OUTPUT

81

Giải thích: Các số có trong xâu ~S~ là ~2144; 81; 9~. Số chính phương lớn nhất tìm được là ~81~.

Ví dụ 2

INPUT

dGaf2leac056Ude00132aV

OUTPUT

-1

Giải thích: Các số có trong xâu ~S~ là ~21; 56; 132~. Không có số chính phương.

Bạn An có một bộ sách hay và muốn chia sẻ với các bạn trong câu lạc bộ đọc sách của trường. Có ~N~ yêu cầu được mượn cuối sách này từ các bạn trong câu lạc bộ, yêu cầu thứ ~i~ ~(1 \le i \le N)~ cho biết thời điểm mượn sách là ~a_i~ và thời điểm trả là ~b_i~. Bạn An có thể chấp nhận hoặc từ chối đối với một yêu cầu.

Yêu cầu

Hãy lập trình giúp bạn An chọn các yêu cầu mượn sách của các bạn sao cho đáp ứng được nhiều yêu cầu nhất. Đảm bảo khoảng thời gian sử dụng của hai yêu cầu là không giao nhau.

Dữ liệu đầu vào

Gồm ~N + 1~ dòng:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(N \le 10^4)~;
• Dòng thứ ~i~ trong số ~N~ dòng tiếp theo chứa hai số nguyên dương ~a_{i},\ b_{i}~ với ~(0 < a_{i} < b_{i} \le 32000)~ ~(1 \le i \le N)~.

Dữ liệu đầu ra

Gồm một số nguyên ~K~ là số các yêu cầu được chấp nhận.

Ràng buộc dữ liệu

• Có 30% số điểm thỏa mãn ~N \le 100;\ a_i < b_i \le 10^3~;
• Có 30% số điểm thỏa mãn ~100 < N \le 10^3;\ a_i < b_i \le 10^3~;
• Có 40% số điểm không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

5
7 9
2 4
1 3
1 6
4 7

OUTPUT

3

Giải thích: Các yêu cầu được chấp thuận là: ~1\ 3; 4\ 7; 7\ 9~.

Số ~X~ được gọi là số đặc biệt nếu tất cả các chữ số của ~X~ đều thuộc tập hợp ~\{1; 3; 5; 7; 9\}~. Người ta tạo ra các số đặc biệt, sau đó sắp xếp chúng theo thứ tự tăng dần để được một dãy số ~A~.

Ví dụ ~20~ số đặc biệt đầu tiên: ~1; 3; 5; 7; 9; 11; 13; 15; 17; 19; 31; 33; 35; 37; 39; 51; 53; 55; 57; 59~.

Yêu cầu

Cho số nguyên dương ~N~, hãy tìm số đặc biệt thứ ~N~ trong dãy số ~A~.

Dữ liệu đầu vào

Gồm một dòng duy nhất chứa số nguyên ~N~ ~(1 \le N \le 10^{18})~.

Dữ liệu đầu ra

Gồm số đặc biệt thứ ~N~ trong dãy số ~A~.

Ràng buộc dữ liệu

• Có 50% số điểm thỏa mãn ~N \le 10^6~;
• Có 30% số điểm thỏa mãn ~10^6 < N \le 10^9~;
• Có 20% số điểm không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

8

OUTPUT

15

Giải thích: Số đặc biệt thứ ~8~ trong dãy là: ~15~. ~1; 3; 5; 7; 9; 11; 13; \underline{15}~.

Ví dụ 2

INPUT

29

OUTPUT

97

Giải thích: Số đặc biệt thứ ~29~ trong dãy là: ~97~. ~1; 3; 5; 7; 9; 11; 13; 15;17; 19; 31; 33; 35; 37; 39; 51; 53; 55; 57; 59; ...; \underline{97}~.