Vào một buổi sáng, rất tình cờ Nam nhìn thấy một số nguyên dương \(N\) trên đường từ nhà đến trường. Vì Nam rất thích số \(30\) nên Nam muốn biến đổi số \(N\) thành số \(M\) có dạng là số lớn nhất và là bội của số \(30\) bằng cách thay đổi vị trí của các chữ số trong số \(N\) mà Nam nhìn thấy.

Bạn hãy hỗ trợ Nam bằng cách viết chương trình để tìm số \(M\) (nếu nó tồn tại).

Input

• Gồm một dòng duy nhất chứa số nguyên \(N\) (\(N\) có tối đa là \(10^5\) chữ số).

Output

• In ra số \(M\) tìm được. Nếu không tồn tại \(M\) thì in ra \(-1\).

Example

30 

30

102

210

3333333333333333333333333333 

-1

Cho xâu \(s\) gồm các kí tự latin (có cả chữ hoa lẫn chữ thường). Nhiệm vụ của bạn là chuyển hoá xâu \(s\) thành \(s'\) theo quy tắc sau:

• Mỗi kí tự nguyên âm trong xâu \(s\) khi chuyển sang \(s'\) đều phải là chữ hoa.

• Mỗi kí tự phụ âm trong xâu \(s\) khi chuyển sang \(s'\) đều phải là chữ thường.

(Ghi chú: Nguyên âm bao gồm những kí tự: \(\left\{u,e,o,a,i\right\}\))

Input

• Dòng thứ nhất chứa số \(t(1\le t\le 100)\) - Thể hiện số testcase

• \(t\) dòng tiếp theo, mỗi dòng chứa một xâu \(s\) (biết rằng xâu \(s\) chứa không quá \(100\) ký tự)

Output

• In ra đáp án cần tìm

Example

4
oikmOP
OOOOk
kkkaAA
ccMMA

OIkmOp
OOOOk
kkkAAA
ccmmA

Có \(N\) viên bi, được đánh số \(1,2,3,...,N\). Với mỗi \(i(1\le i\le N)\), viên bi thứ \(i\) có khối lượng là \(w_i\) và có giá trị là \(v_i\).

\(Kaninho\) quyết định chọn một số viên bi từ \(N\) viên bi trên và bỏ vào ba lô để đi chơi. Sức chứa của ba lô là \(W\), có nghĩa là tổng khối lượng của các viên bi được chọn phải không được quá \(W\).

Tìm tổng giá trị lớn nhất có thể của các viên bi được chọn để bỏ vào ba lô.

Input

• Dòng thứ nhất chứa hai số nguyên \(N,W(1\le N\le 100,1\le W\le 10^5)\)

• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(w_i,v_i(1\le w_i\le W,1\le v_i\le 10^9)\)

Output

• In ra giá trị cần tìm.

Example

3 8
3 30
4 50
5 60

90