Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P184PROG - ROUND 4G - Xâu hoán vị cực đại

Một xâu kí tự S độ dài n được biểu diễn dưới dạng S1S2S3…Sn trong đó Si là kí tự thứ i của xâu S. Một xâu P là xâu hoán vị của xâu S nếu P = Sp1Sp2Sp3…Spn, trong đó p1, p2, p3, …, pn là một bộ hoán vị của các số tự nhiên từ 1 đến n.

Cho 2 xâu kí tự T và V. Trong các xâu hoán vị của T, hãy tìm ra xâu có số lần xuất hiện trong xâu V là nhiều nhất. Nếu có nhiều xâu như vậy, chọn ra xâu có thứ tự từ điển nhỏ nhất.

Input

Dòng đầu gồm một số nguyên dương Q (1 ≤ Q ≤ 3) là số bộ test.

Mỗi bộ test gồm 2 dòng, dòng đầu tiên là xâu T, dòng thứ 2 là xâu V (1 ≤ |T| ≤ 20000, 1 ≤ |V| ≤ 200000, |T| ≤ |V|).

Các xâu ký tự chỉ gồm các chữ cái tiếng Anh viết thường.

Output

Với mỗi bộ test, in ra trên một dòng xâu hoán vị tìm được. Nếu không có xâu nào thoả mãn, in ra -1.

Example

Input:
2
tan
tantant
t
v Output: ant
-1
Giải thích:
Ở ví dụ 1, xâu ‘tan’ có 3 xâu hoán vị xuất hiện trong xâu ‘tantant’ là ‘ant’, ‘nta’ và ‘tan’. Trong đó ‘ant’ và ‘tan’ cùng có số lần xuất hiện lớn nhất là 2, do đó ta chọn ‘ant’ vì nó có thứ tự từ điển nhỏ hơn.

Được gửi lên bởi:Admin
Ngày:2018-03-23
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.