Một ông già rảnh hơi nào đó đã viết cho Loli ~Q~ số nguyên và bảo Loli phải kiểm tra xem số đó có phải là số nguyên tố không. Nếu Loli trả lời đúng hết thì ông già sẽ mời Loli về nhà riêng của mình…

Input:

Vào từ file văn bản NTO.INP gồm:

• Dòng ~1~: chứa số nguyên dương ~Q~ ~(1 \le Q \le 10^5)~.
• Dòng ~2~ đến dòng ~Q+1~: dòng ~i+1~ chứa số nguyên ~a[i]~ cần kiểm tra ~(|a[i]| \le 10^6)~.

Output:

Ghi ra file văn bản NTO.OUT gồm:

• ~Q~ dòng, dòng ~i~ là kết quả kiểm tra tính nguyên tố của số nguyên ~a[i]~. Nếu không là số nguyên tố, in ra Yes, ngược lại, in ra No.

Ví dụ:

NTO.INP

1
3

NTO.OUT

No

Số chính phương là bình phương của một số nguyên. Ví dụ, ~1 = 1^2~, ~4870849 = 2207^2~ và ~31393609 = 5603^2~ là các số chính phương, còn ~2~, ~8~ hay ~10~ thì không. Trong bài toán này, ta chỉ xét các số chính phương là bình phương của một số nguyên dương.

Ta gọi một số là số chính phương không lặp lại khi và chỉ khi số đó là số chính phương và trong biểu diễn của số đó trong hệ thập phân, không có chữ số nào xuất hiện nhiều hơn một lần. Ví dụ, ~25 = 5^2~, ~36 = 6^2~ và ~49 = 7^2~ là các số chính phương không lặp lại, còn ~100 = 10^2~, ~121 = 11^2~ và ~144 = 12^2~ thì không (vì có các chữ số ~0~, ~1~ hay ~4~ xuất hiện nhiều hơn một lần).

Ta viết các số chính phương không lặp lại dương thành một dãy và sắp xếp chúng theo thứ tự tăng dần, ta được dãy ~1, 4, 9, \dots~

Yêu cầu: Cho một số nguyên dương ~k~, hãy tìm số thứ ~k~ trong dãy.

Input:

• Một số nguyên duy nhất ~k~ ~(1 \le k \le 10^{18})~.

Output:

• Một số nguyên là số chính phương không lặp lại lớn thứ ~k~. Nếu số này không tồn tại, in ra ~-1~.

Sample Input 1

9

Sample Output 1

81

Sample Input 2

10

Sample Output 1

169

Mọi người dân vô tội đang phải chịu một điều luật hà khắc do Loli rảnh rỗi sinh nông nổi tạo ra, có tên là CLGT. Bộ luật đã thay đổi hoàn toàn cách người dân tính toán các số. Ở bài toán này các bạn cần tìm "cội nguồn" của một số. Theo điều luật CLGT, "cội nguồn" là tổng các chữ số của một số nguyên, lấy số đó tính đi tính lại cho tới khi nó trở thành số có một chữ số.

Input:

• Một số nguyên dương ~N~ duy nhất ~(1 \le N \le 10^{18})~.

Output:

• Một số nguyên dương là đáp án của bài toán.

Sample Input 1

1

Sample Output 1

1

Sample Input 2

81

Sample Output 2

9

Sample Input 3

1624

Sample Output 3

4

Giải thích

• Ở test 1, cách biến đổi sẽ là: ~1 \rightarrow 1~.
• Ở test 2, cách biến đổi sẽ là: ~81 \rightarrow 9~.
• Ở test 3, cách biến đổi sẽ là: ~1624 \rightarrow 13 \rightarrow 4~.

Dạo một vòng Facebook, Loli cảm thấy rất chán khi thấy giới trẻ cứ thấy cái gì đấy là lại muốn "uoc j uoc j". Vì vậy Loli nhờ các bạn coder giải quyết vấn nạn nhức nhối này bằng việc tạo ra chương trình trả lời hết các câu "uoc j".

Input:

• Dòng đầu tiên chứa một số nguyên ~j~ ~(1 \le j \le 10^{12})~.

Output:

• Gồm một dãy số nguyên tăng dần là ước của ~j~.

Sample Input 1

3

Sample Output 1

1 3

Sample Input 2

69

Sample Output 2

1 3 23 69

Nam là một người mới bắt đầu học lập trình. Hôm nay Nam học về mảng. Anh ấy có một mảng ~n~ số nguyên dương là ~a_1, a_2, \dots, a_n~. Giáo viên của anh cho một nhiệm vụ, tìm một số ~x~ trong mảng thoả mãn: tất cả các số khác trong mảng đều chia hết cho số ~x~ đó. Hãy giúp anh ấy tìm ra số ~x~ đó!

Input:

File "SNUM.INP" gồm:

• Dòng đầu chứa số nguyên ~n\ (1\le n \le 10^5)~, cho biết số lượng số nguyên dương trong mảng.
• Dòng thứ hai gồm các số nguyên ~a_1, a_2, \dots, a_n\ (1 \le a_i \le 10^9)~, là các phần tử của mảng.

Output:

File "SNUM.OUT":

• Ghi một số nguyên ~x~ duy nhất, sao cho tất cả các số khác trong mảng đều chia hết cho số ~x~ đó.
• Nếu số đó không tồn tại, đưa ra ~-1~.

Ví dụ 1:

SNUM.INP

3
2 2 4

SNUM.OUT

2

Ví dụ 2:

SNUM.INP

5
2 1 3 1 6

SNUM.OUT

1

Ví dụ 3:

SNUM.INP

3
2 3 5

SNUM.OUT

-1

Chàng sinh viên IT trẻ thấy một cậu bé cấp II đang cúp học chơi net, chàng ta liền tiến lại bắt chuyện.

- Mai mốt lớn lên, em muốn làm gì?

- Em thích game lắm, lớn lên em sẽ làm game ạ!

- Thế em biết làm game cần những cái gì không?

- Tất nhiên là có rồi. Đó chính là đam mê với máy tính!

Chàng sinh viên lặng người. Những ký ức ác mộng về quá trình sản xuất game độc lập. Nào là thuật toán, nào là thiết kế đồ họa, thiết kế giao diện người dùng, sản xuất nhạc, tối ưu hóa, vật lý cao cấp, toán cao cấp, lập trình, ... cứ thế chạy qua trong tâm trí của anh.

Anh nhớ lại, đã có một thời mình cũng từng ngây thơ như vậy, đôi mắt của mình cũng từng sáng như cậu bé này, sự nhiệt huyết tuổi trẻ mà anh đã đánh mất. Tất cả điều đó khiến mắt anh nhòe đi. Giờ đây nhìn lại mình. Chàng sinh viên thấy mình đã già, mắt đã cận, lưng còng, đít trĩ, tay run.

"Không, không thể như thế được! Mình phải bảo vệ đôi mắt ngây thơ này!".

Thế là anh đè cậu bé ra đấm túi bụi, vừa đấm vừa chửi:

- Á à, cúp học chơi gêm còn bày đặt lày! Láo này! Học không lo học suốt ngày gêm!

*bốp *bốp *bốp

Cậu bé vừa xách quần chạy vừa chửi thầm trong đầu. Còn anh sinh viên thì nấp sau góc tường, ngồi phệt xuống sàn và suy nghĩ câu hỏi sau: "Cho một số nguyên dương ~N~. Tìm số nhỏ nhất chỉ gồm chữ số ~1~ chia hết cho ~N~".

Input:

• Gồm một số nguyên dương ~N~ ~(1 \le N \le 2 \times 10^6)~.

Output:

• Gồm một số nguyên dương là số cần tìm. Nếu không có kết quả in ra ~-1~. Nếu có kết quả, đề bài đảm bảo kết quả không vượt quá ~10^{10^7}~.

Subtasks:

• ~20\%~ số test không có kết quả hoặc có kết quả không vượt quá ~10^7~.
• ~20\%~ số test có kết quả không vượt quá ~10^{18}~.
• ~30\%~ số test có kết quả không vượt quá ~10^{727}~.
• ~30\%~ số test không có ràng buộc gì thêm.

Sample Input 1

69

Sample Output 1

111111111111111111111111111111111111111111111111111111111111111111

Sample Input 2

420

Sample Output 2

-1

Giải thích:

• Ở test 1, ~111111111111111111111111111111111111111111111111111111111111111111/69 = 1610305958132045088566827697262479871175523349436392914653784219~ và dư ~0~.
• Ở test 2, một số chia hết cho ~420~ luôn kết thúc bằng chữ số ~0~, nhưng nó là điều bất khả thi vì số toàn ~1~, như việc tôi có người yêu vậy…

Tôi chẳng biết trong đầu em đang nghĩ gì... Xung quanh em có quá nhiều người bạn, cũng thừa những người theo đuổi em... Khi mọi người đã ngủ say, và có lẽ cả em cũng vậy, tôi lại tự hỏi rằng liệu em có đang mơ về ai kia, hay tôi lại may mắn được làm ai kia trong giấc mơ của em?

Mơ... Gặp được em đã là một trong những thứ điên tới mức tôi chẳng bao giờ mơ về, đặc biệt với một người mà ai ai cũng biết tới. Thậm chí ngay từ đầu tại sao tôi lại gặp được em cơ chứ? Và có lẽ tài năng như em thì tôi làm gì có cơ hội?

Ai biết được nhỉ? Điều tôi biết duy nhất là bây giờ, sâu trong giấc ngủ em đang mơ về ai đó, trong khi tôi đang mơ về một thuật toán đúng để giải bài toán sau đây:

Cho số nguyên dương ~N~, hãy tính ~S = 1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \dots + N(N+1)~.

Input:

• Gồm một số nguyên dương ~N\ (1 \le N \le 10^9)~.

Output:

• Gồm một số nguyên dương là số dư của ~S~ trong phép chia cho ~177013~.

Sample Input

3

Sample Output

20

Giải thích

Ta có: ~S=1 \cdot 2+2 \cdot 3+3 \cdot 4=20~.

Ràng buộc

• 50% số test có ~N \le 10^4~.
• 30% số test có ~N \le 10^7~.
• 20% số test không có ràng buộc gì thêm.

Nam làm nghề thợ xây. Anh có ~n~ viên gạch được đánh số từ ~1~ tới ~n~. Nhiệm vụ của anh là phải sơn những viên gạch này. Một viên gạch sẽ được sơn màu đỏ nếu chỉ số của nó chia hết cho ~a~. Một viên gạch sẽ được sơn màu xanh da trời nếu chỉ số của nó chia hết cho ~b~. Viên gạch mà chỉ số của nó đều chia hết cho ~a~ và ~b~ có thể được sơn màu đỏ hoặc màu xanh da trời.

Sau khi sơn gạch, Nam sẽ nhận được ~p~ miếng sô cô la cho mỗi viên gạch sơn màu đỏ và ~q~ miếng sô cô la cho mỗi viên gạch sơn màu xanh.

Lưu ý rằng Nam có thể sơn gạch theo bất kỳ thứ tự nào anh ấy muốn. Tìm số lượng sô cô la lớn nhất Nam có thể nhận.

Input:

• File "PAINT.INP" gồm một dòng duy nhất chứa ~5~ số nguyên ~n, a, b, p~ và ~q~ ~(1 \le n,a,b,p,q \le 10^9)~

Output:

• File "PAINT.OUT" ghi duy nhất số nguyên ~s~ là số miếng sô cô la lớn nhất mà Nam có thể nhận.

Sample Input 1

5 2 3 12 15

Sample Output 1

39

Sample Input 2

20 2 3 3 5

Sample Output 2

51

Vào mùng 1 Tết, Loli vì ham chơi nên đã quên lì xì cho bạn gái của mình và chuyện gì đến rồi cũng đã đến: Bạn gái của anh ấy muốn kết thúc cuộc tình của hai người tại đây vì hành động sơ ý đó của chàng trai. Tuy nhiên, vì là một người đã cô đơn rất lâu rồi và giờ mới có được một mảnh tình vắt vai nên Loli đã năn nỉ, thuyết phục cô bạn gái tha thứ cho mình. Bạn gái của anh ta đã đồng ý tha thứ cho anh ấy với điều kiện là anh ta phải giải được một mê cung tình ái mà cô ấy ra cho anh, nếu không thì Loli sẽ chính thức trở thành một thằng "thiếu nữ" vĩnh viễn.

Mê cung tình ái này là một cái bảng có kích cỡ vô hạn như tình yêu anh dành cho em, với ô trên cùng bên trái có số ~1~. Hình bên dưới là 5 lớp đầu tiên của mê cung.

Cô ta muốn Loli tìm được giá trị ở ô tại hàng ~x~ và cột ~y~. Bạn hãy giúp Loli cứu lấy cuộc tình của anh ấy.

Input:

• Dòng đầu tiên chứa một số nguyên dương ~T\ (1 \le T \le 10^5)~ là số lượng truy vấn.
• Sau đó là ~T~ dòng, mỗi dòng chứa hai số nguyên ~x, y\ (1 \le x,y \le 10^9)~.

Output:

• Gồm ~T~ dòng, in ra trên một dòng một số nguyên thể hiện giá trị của ô tại hàng ~x~ và cột ~y~.

Sample Input

4
1 1
2 3
4 2
6 7

Sample Output

1
8
15
44

Con mèo dí súng vào đầu con chó rồi hỏi:

- 1+1 = mấy?

- Dạ! = 2 ạ!

'Pằng', con mèo thổi khói súng: Mày đã biết quá nhiều.

Vẫn câu hỏi đó, con chó thứ 2 suy nghĩ rồi run rẩy trả lời:

- Dạ! em không biết ạ!

'Pằng', con mèo lại thổi khói: Loại dốt nát như mày không nên sống.

Đến con chó thứ 3, mèo vẫn hỏi lại câu hỏi đó. Con này suy nghĩ rồi trả lời:

- Biết thì sao mà không biết thì sao?

'Pằng'!: Nguy hiểm như mày thì càng phải chết.

Tiếp tục con chó thứ 4, lại là câu hỏi đó, con này suy nghĩ rồi trả lời:

- Trả lời anh giết, không trả lời anh giết, trả lời sai anh giết, trả lời đúng cũng giết luôn, thì em biết phải làm sao?

'Pằng'!: Mày phải chết vì mày nói quá nhiều.

Đến con cuối cùng, vẫn câu hỏi cũ, con này nhanh nhảu trả lời:

- Dạ thưa anh! Với những câu hỏi hóc búa như vậy, thì chỉ có những người cao siêu như anh mới có đáp án chính xác ạ!

Con mèo khoái chí bảo: Mày được, theo tao!

Yêu cầu: Theo bạn, ~1+1\ =\ ?~

Input:

• Không có Input.

Output:

• Đáp án cần tìm.