Tuấn Anh là một người đam mê ngoại ngữ và anh ấy vừa xây dựng thành công một cỗ máy Suffix Three nhận biết ngôn ngữ hoạt động như sau, khi nhập vào một xâu kí tự thì cỗ máy sẽ phát hiện xâu kí tự đó là ngôn ngữ của nước nào theo quy tắc như sau :

• Nếu xâu kết thúc bằng "po" thì xâu đó là ngôn ngữ Filipino.
• Nếu xâu kết thúc bằng "desu" hoặc "masu" thì xâu đó là ngôn ngữ Japanese.
• Nếu xâu kết thúc bằng "mnida" thì xâu đó là ngôn ngữ Korean

Bạn hãy viết chương trình mô phỏng lại cỗ máy đó !

Input

Dòng đầu tiên gồm 1 số nguyên t ~(1 \le T \le 30)~, số lượng xâu bạn cần xử lí.

T dòng tiếp theo, mỗi dòng gồm một xâu S ~(1 \le |S| \le 10^5)~

Output

Với mỗi xâu S hãy in ra ngôn ngữ của xâu đó.

Bộ test đảm bảo rằng tất cả các xâu chỉ có kết thúc bằng "po", "desu", "masu" hoặc "mnida".

Sample Input

8
kamusta_po
genki_desu
ohayou_gozaimasu
annyeong_hashimnida
hajime_no_ippo  
bensamu_no_sentou_houhou_ga_okama_kenpo
ang_halaman_doon_ay_sarisari_singkamasu 
si_roy_mustang_ay_namamasu

Sample Output

FILIPINO
JAPANESE
JAPANESE
KOREAN
FILIPINO
FILIPINO
JAPANESE
JAPANESE

Nguồn đề : codeforces

Cho hai số nguyên dương n và k. Hiển thị ra màn hình số nguyên dương thứ k không chia hết cho n.

Ví dụ : n = 3, k = 7, các số nguyên dương không chia hết cho 3 lần lượt là 1, 2, 4, 5, 7, 8, 10, 11, 13 ... vậy số nguyên dương thứ 7 không chia hết cho 3 là 10.

Input

Dòng đầu tiên gồm 1 số nguyên t ~(1 \le T \le 1000)~, số lượng test.

T dòng tiếp theo mỗi dòng chứa 2 số nguyên dương n ~(1 \le n \le 10^9)~ và k ~(1 \le k \le 10^9)~

Output

Với mỗi dòng n và k, in ra số nguyên dương thứ k không chia hết cho n.

Sample Input

6
3 7
4 12
2 1000000000
7 97
1000000000 1000000000
2 1

Sample Output

10
15
1999999999
113
1000000001
1

Nguồn đề : https://codeforces.com/contest/1352/problem/C

Đạt đi du lịch bằng tàu điện ngầm. Mọi người biết rằng vé tàu điện ngầm một lần đi có giá a đồng. Bên cạnh đó, Đạt phát hiện ra rằng anh ấy có thể mua một vé tàu đặc biệt cho m lần đi (anh ấy có thể mua nhiều lần). Nó có giá b đồng. Đạt đã làm toán, anh ấy cần sử dụng đi tàu điện ngầm n lần. Giúp Đạt, cho anh ấy biết số tiền tối thiểu anh ấy sẽ phải chi để thực hiện n chuyến đi là bao nhiêu tiền?

Không nhất thiết phải mua đúng n vé

Input

Dòng duy nhất chứa 4 số nguyên n, m, a, b (1 ≤ n, m, a, b ≤ 10000) – số chuyến đi Đạt đã lên kế hoạch, số chuyến đi được bao gồm trong vé đi xem, giá vé một chuyến, giá vé m.

Output

Số nguyên x – số tiền tối thiểu (Tính bằng đồng) mà Đạt phải trả cho n chuyến đi.

Sample Input

6 2 1 2

Sample Output

6

update problem's source after contest : https://codeforces.com/contest/1133/problem/A

setter's soluion : https://codeforces.com/contest/1133/submission/110623261

Tuấn Anh là một học sinh tài năng của khóa 18 FITHOU, với thành tích học tập đáng nể kì nào anh cũng được học bổng loại giỏi, nên anh ta trở nên nổi tiếng toàn trường. Vì là sinh viên giỏi, nên anh rất được các bạn nữ ái mộ. Một hôm, có một bạn nữ hỏi anh: "Thời gian tự học của Tuấn Anh - kun bắt đầu và kết thúc khi nào?", Tuấn Anh nói anh ấy học từ h1 : m1 đến h2 : m2 và quy định của anh ấy là: thời gian học kéo dài theo số phút chẵn, toàn bộ thời gian học chỉ được trong 1 ngày để đảm bảo sức khỏe và tối thiểu thời gian học phải kéo dài ít nhất 2 phút (người học giỏi thật là có những quy định thật kì lạ).

Sau khi các bạn nữ đã thỏa mãn với câu trả lời của Tuấn Anh, anh ấy lại tiếp tục suy nghĩ với câu trả lời của mình, anh ta nhận ra mình dễ dàng tìm ra mốc thời gian chính giữa của khoảng thời gian mình đã học. Điều này khá dễ dàng với Tuấn Anh, nên Tuấn Anh đã đem bài tập này dành cho Hải (là học sinh cá biệt của lớp), các bạn hãy giúp Hải giải quyết bài toán này để Hải không bị Tuấn Anh chửi nào ^^

Ví dụ: Nếu Tuấn Anh học từ 10:00 đến 14:00 thì mốc thời gian chính giữa là 12:00

Input

Dòng đầu chứa 2 số nguyên h1 và m1 theo định dạng hh:mm

Dòng đầu chứa 2 số nguyên h2 và m2 và cũng theo theo định dạng hh:mm

Điều kiện: 0 <= h1, h2 <= 23 và 0 <= m1, m2 <= 59

Và 2 mốc thời gian phải đảm bảo quy định của Tuấn Anh (như trên)

Output

In ra 2 số h3 và m3 (0 <= h3 <= 23, 0 <= m3 <= 59) tương đương với mốc giữa của thời gian Tuấn Anh học theo định dạng hh:mm. In mỗi số chính xác 2 chữ số (có thể thêm tiền tố 0 nếu cần), ngăn cách chúng với ':'

Input 01

10:00

11:00

output 01

10:30

Input 02

11:10

11:12

output 02

11:11

Hôm nay là một ngày đẹp trời nhưng đầy nắng gió, Aha đi ăn lẩu nướng ở quán BaHa nhưng lại hết tiền. Bình thường 1 suất ăn hết 266 VND, nhưng hôm nay lại là sinh nhật của chủ quán nên chủ quán sẽ khuyến mãi ăn free cho ai giải được bài toán anh ta đưa ra. Aha rất thích ăn mà không muốn làm. Vì vậy anh ấy nhờ bạn giải giúp bài toán của nhà hàng đưa ra. Vấn đề cần giải quyết như sau: Cho hai mảng không tăng các số nguyên A, B tức là A[i] ≥ A[i + 1] và B[i] ≥ B[i + 1] và với mọi i, 0 ≤ i < n-1. Ta định nghĩa BaHa của hai số được cho bởi công thức: M (A[i], B[j]) = j - i , nếu j ≥ i và B[j] ≥ A[i], hoặc 0 nếu ngược lại.

Nếu ai tìm được Baha lớn nhất trong tất cả Baha thì sẽ được ăn free , tức là: M (A, B) = max (M (A[i], B[j])) với 0 ≤ i, j < n-1. Hãy giúp Baha được ăn free nhé mọi người, nếu được Baha sẽ cho bạn 1 cái kẹo để cảm ơn .

Input

Dòng đầu tiên gồm 1 số nguyên t ~(1 \le T \le 50)~, số lượng test.

Mỗi test sẽ gồm 3 dòng :

Dòng đầu tiên gồm 1 số nguyên n ~(2 \le n \le 10^5)~, số lượng phần tử của mỗi mảng.

Dòng thứ hai gồm dãy n số nguyên ai ~(1 \le ai \le 10^{12})~.

Dòng thứ ba gồm dãy n số nguyên bi ~(1 \le bi \le 10^{12})~.

Output

Với mỗi test in ra số Baha lớn nhất.

Sample Input

2
9
7 7 3 3 3 2 2 2 1
8 8 7 7 5 5 4 3 2
6
6 5 4 4 4 4
2 2 2 2 2 2

Sample Output

5
0

Nguồn đề : https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/algorithm/the-old-monk/?fbclid=IwAR0Wgh24JmU1mR2kTWnXDdeBt9xdpGj9IUKbJtmKRjisSod9yJBuRn8IiqA

Cho một dãy số, với mỗi phần tử A của dãy hãy tìm phân tử gần nhất bên phải gọi là phần tử đó B, có số lần suất xuất hiện lớn hơn A. Nếu không tồn tại B thỏa mãn, in ra -1.

Input

Dòng đầu tiên gồm 1 số nguyên t ~(1 \le T \le 100)~, số lượng test.

Mỗi test sẽ gồm 2 dòng :

Dòng đầu tiên gồm 1 số nguyên n ~(1 \le n \le 10^5)~, số lượng phần tử của dãy.

Dòng thứ hai gồm dáy n số nguyên ai ~(1 \le ai \le 10^5)~, với ai là giá trị của phần tử thứ i.

Output

Gồm n số nguyên d1, d2, d3, .. dn, với di là phần tử phải nhất thỏa mãn điều kiện.

Sample Input

3
10
1 3 7 2 5 1 4 2 1 5
5
1 1 1 1 1
6
1 1 2 2 2 3

Sample Output

-1 2 2 1 1 -1 2 1 -1 -1 
-1 -1 -1 -1 -1 
2 2 -1 -1 -1 -1

Nguồn : https://www.hackerearth.com/practice/data-structures/stacks/basics-of-stacks/practice-problems/algorithm/signal-range/