Cho một chuỗi ký tự ~S~ gồm toàn chữ cái tiếng Anh in thường, hãy tìm vị trí đầu tiên của ký tự xuất hiện duy nhất một lần trong ~S~. Các ký tự trong chuỗi được đánh thứ tự từ ~1,2, \ldots~ nếu không có lý tự nào như vậy thì in ra số ~-1~.

Dữ liệu:

• Dòng đầu tiên của đầu vào chứa số nguyên ~q(1 \leq q \leq 100)~ là số truy vấn.
• Tiếp theo là ~q~ dòng, mỗi dòng chứa một truy vấn là một chuỗi ký tự ~S~ có độ dài không quá ~200~.

Kết quả:

• Chương trình của bạn cần in ra ~q~ dòng, trong đó dòng thứ ~i~ ghi câu trả lời của truy vấn thứ ~i~ theo yêu cầu đề bài.

Ví dụ:

Sample Input

4 
abcdbc
abcdefabcde 
ababab 
a

Sample Output

1
6
-1
1

Ràng buộc:

• Có ~75\%~ số test, ứng với ~75\%~ số điểm của bài có độ dài các chuỗi ~S~ không quá ~10~;
• Có ~25\%~ số test còn lại, ứng với ứng với ~25\%~ số điểm của bài có độ dài các chuỗi ~S~ không quá ~200~.

Cho phương trình: $$ x^2+S(x) x-N=0 $$ Trong đó ~x, N~ là những số nguyên dương, ~S(x)~ bằng tổng các chữ số của ~x~.

Yêu cầu: Cho trước giá trị ~N~. Hãy tìm giá trị ~x~ nhỏ nhất thỏa mãn phương trình trên.

Dữ liệu:

• Gồm một số nguyên duy nhất ~N\left(1 \leq N \leq 10^{18}\right)~.

Kết quả:

• Ghi ra một số nguyên duy nhất ~x~ nhỏ nhất thỏa mãn phương trình. Trong trường hợp không tìm được ~x~ thì ghi ra ~-1~ .

Ví dụ:

Sample Input 1

2

Sample Output 1

1

Sample Input 2

4

Sample Output 2

-1

Ràng buộc:

• Có ~40 \%~ số test ứng với ~40 \%~ số điểm của bài có ~N \leq 10^4~;
• Có ~30 \%~ số test khác ứng với ~30 \%~ số điểm của bài có ~N \leq 10^{10}~.
• Có ~30 \%~ số test còn lại ứng ~30 \%~ số điểm của bài có ~N \leq 10^{18}~.

Xét trò chơi xếp hình chữ nhật với các que diêm như sau: Có ~n~ que diêm, que thứ ~i~ có độ dài ~d_i~. Người chơi cần chọn ra 4 que diêm để có thể xếp thành một hình chữ nhật, giả sử ~4~ que diêm mà người chơi chọn có độ dài lần lượt là ~a, b, c, d(a \leq b \leq c \leq d)~, khi đó có thể xếp được thành một hình chữ nhật nếu ~a=b~ và ~c=d~. Người chơi xếp được hình chữ nhật có diện tích càng lớn sẽ càng được điểm cao.

Yêu cầu: Cho ~d_1, d_2, \ldots, d_n~ là độ dài của ~n~ que diêm. Hãy tìm cách chọn ~4~ que diêm để xếp được thành một hình chữ nhật có diện tích lớn nhất.

Dữ liệu:

• Dòng đầu tiên ghi số nguyên dương ~K~ là số lượng bộ dữ liệu. Tiếp đến là ~K~ nhóm dòng, mỗi nhóm tương ứng với một bộ dữ liệu có cấu trúc như sau:
  • Dòng thứ nhất ghi một số nguyên dương ~n~;
  • Dòng tiếp theo chứa ~n~ số nguyên dương ~d_1, d_2, \ldots, d_n\left(d_i \leq 10^9\right)~.

Kết quả:

• Ghi ra gồm ~K~ dòng, mỗi dòng ghi một số nguyên là diện tích của hình chữ nhật xếp được tương ứng với bộ dữ liệu trong file dữ liệu vào (ghi -1 nếu không tồn tại cách chọn nào xếp được hình chữ nhật).

Ví dụ:

Sample Input

2
5
5 3 1 5 1
4
1 2 3 4

Sample Output

5
-1

Ràng buộc:

• Có ~40\%~ số test, ứng với ~40\%~ số điểm của bài có ~n \leq 30~;
• Có ~40\%~ số test, ứng với ~40\%~ số điểm của bài có ~n \leq 3000~;
• Có ~20\%~ số test còn lại, ứng với ~20\%~ số điểm của bài có ~n \leq 300000~.

Hãng cung cấp dịch vụ điện thoại ~XYZ~ khuyến khích nhiều người đăng kí thuê bao bằng cách: Khi khách hàng đến đăng ký thuê bao thì sẽ được cấp hai số may mắn là số nguyên dương ~n~ và ~k~, hãng sẽ khuyến mại người đó một số tiền nhận được từ số ~n~ sau khi xóa đúng ~k~ chữ số (~k~ nhỏ hơn số chữ số của ~n~).

Nam vừa mới đăng ký thuê bao của hãng và được cung cấp hai số ~n~ và ~k~, bạn hãy giúp Nam xóa đi ~k~ chữ số của số ~n~ để số nhận được là lớn nhất.

Dữ liệu:

• Dòng thứ nhất là số ~n~ (số chữ số của ~n \leq 10^5~);
• Dòng thứ hai là số ~k~ (~k \lt n~).

Kết quả:

• Một dòng duy nhất là số lớn nhất có được sau khi xóa đi ~k~ chữ số của ~n~.

Ví dụ:

Sample Input 1

58816
2

Sample Output 1

886

Sample Input 2

2357111317192329
6

Sample Output 2

7317192329

Ràng buộc:

• Có ~30\%~ số test, ứng với ~30\%~ số điểm của bài có số chữ số của ~n \leq 100~;
• Có ~30\%~ số test, ứng với ~30\%~ số điểm của bài có số chữ số của ~n \leq 255~;
• Có ~40\%~ số test còn lại, ứng với ~40\%~ số điểm của bài có số chữ số của ~n \leq 10^5~.