📌 Lưu ý:

• Được phép sử dụng code đã công khai trên các diễn đàn. Nếu được, các bạn nên ghi rõ nguồn để tránh bị chúng mình kiểm tra nhầm.
• Một tài khoản chỉ do một người làm.
• Nghiêm cấm sử dụng công cụ trí tuệ nhân tạo can thiệp vào bài làm.
• Nghiêm cấm chia sẻ code, chép code hoặc trao đổi.
• Không mã hóa code, ví dụ như sau.
• Vi phạm một trong những điều trên, tài khoản của bạn sẽ bị disqualify khỏi contest và không được xét giải. Nếu ~> 1~ lần bị ban khỏi các contest tính rated của ClueOJ, tài khoản của bạn sẽ bị cấm vĩnh viễn trên nền tảng này.
• Trong mọi trường hợp, quyết định của BTC là quyết định cuối cùng.

Lời cuối, chúc các bạn làm bài tốt.

Cho hai số nguyên ~a~ và ~b~. Hãy tính ~a + b~.

INPUT

Hai số nguyên ~a~ và ~b~ (~0 \le |a|, |b| \le 200~).

OUTPUT

Giá trị ~a + b~.

SAMPLE INPUT

2 2

SAMPLE OUTPUT

4

Cho hai số nguyên ~b~ và ~a~. Hãy tính ~|b + a|~.

INPUT

Hai số nguyên ~b~ và ~a~ (~0 \le |b|, |a| \le 200~).

OUTPUT

Kết quả bài toán.

SAMPLE INPUT

2 2

SAMPLE OUTPUT

4

Bài toán này và Trò chơi trên lá bài (hard version) là hai bài hoàn toàn khác nhau.

Đây là bài toán tương tác.

Bạn được noodles0428 rủ chơi bài. Trên tay cô ấy là ~n~ (~1 \le n \le 50~) lá bài, là một hoán vị từ ~1~ đến ~n~. Tất nhiên, bạn không biết vị trí của từng lá bài.

Luật chơi của trò chơi này như sau:

• Bạn được quyền đặt câu hỏi dưới dạng: 1 i j, với ~i \neq j~, nghĩa là bạn sẽ yêu cầu noodles0428 trả về kết quả:
  • > nếu giá trị lá bài thứ ~i >~ giá trị lá bài thứ ~j~.
  • < nếu giá trị lá bài thứ ~i <~ giá trị lá bài thứ ~j~.
• Bạn được phép hỏi tối đa ~5000~ truy vấn, và cuối cùng, bạn phải xuất ra dãy giá trị của các lá bài theo thứ tự vị trí từ ~1~ đến ~n~. Bạn sẽ chiến thắng nếu như dãy giá trị mà bạn đoán hoàn toàn trùng khớp với dãy lá bài mà noodles0428 đang cầm.

TƯƠNG TÁC

• Bạn cần nhập ~n~, là số lá bài mà noodles0428 đang cầm.
• Nếu là lượt của bạn, bạn có hai lựa chọn sau:
  • Nếu bạn chưa biết đáp án: bạn có quyền đặt câu hỏi cho noodles0428 có dạng 1 i j, với ~i \neq j~, trên một dòng.
  • Nếu bạn đã có đáp án: bạn hãy in ra một dãy số có dạng như sau: 2 a_1, a_2, a_3, ..., a_n với ~a_i~ là giá trị của lá bài tại vị trí thứ ~i~, trên một dòng. Kết thúc lượt này, chương trình sẽ ngắt.
• Nếu là lượt của noodles0428, cô ấy sẽ trả lời truy vấn của bạn dưới dạng > hoặc <.

SAMPLE

Bài toán này và Trò chơi trên lá bài (easy version) là hai bài hoàn toàn khác nhau.

Đây là bài toán tương tác.

"Ái chà, thú vị đấy."

Đó là lời tán thưởng của noodles0428 khi bạn đã hoàn thành Trò chơi trên lá bài một cách hoàn toàn thuyết phục. Chính vì thế, cô ấy quyết định rủ bạn chơi một trò chơi nữa để thử thách khả năng suy luận của bạn.

Luật chơi như sau:

Trên tay noodles0428 đang có hai loại lá bài - trắng và đen. Nhiệm vụ của bạn là hãy xác định vị trí của một lá bài màu trắng bất kỳ.

Để có thể xác định màu của lá bài, bạn có thể đặt câu hỏi dưới dạng 1 i j với ý nghĩa như sau:

• Nếu lá bài thứ ~i~ là lá bài màu trắng, noodles0428 sẽ nói thật về màu của lá bài thứ ~j~.
• Nếu lá bài thứ ~i~ là lá bài màu đen, noodles0428 sẽ nói ngẫu nhiên về màu của lá bài thứ ~j~. Tức là cũng có thể là nói thật, và cũng có thể là nói dối. Tuy vậy, với mỗi lá bài ~i~ màu đen, bất luận bạn hỏi bao nhiêu lần, noodles0428 cũng sẽ nói dối hết, hoặc nói thật hết. Điều này có nghĩa, với mỗi lá bài ~i~ màu đen, việc nói dối hay thật là cố định.
• Máy chấm sẽ trả về ~1~ nếu noodles0428 nói lá bài thứ ~j~ là lá bài màu đen, và ~0~ nếu cô ấy nói lá bài thứ ~j~ là lá bài màu trắng.

Bạn biết được một thông tin cực kì quan trọng: số lá bài màu trắng nhiều hơn số lá bài màu đen. Ví dụ, có ~5~ lá bài, sẽ có ít nhất ~3~ lá bài màu trắng. Bạn sẽ chiến thắng nếu bạn xác định được vị trí của một lá bài màu trắng bất kỳ mà không hỏi noodles0428 quá ~5000~ truy vấn.

TƯƠNG TÁC

• Đầu tiên, bạn cần nhập số nguyên dương ~n~ (~1 \le n \le 1000~), là số lá bài mà noodles0428 đang cầm.
• Nếu là lượt của bạn, bạn có hai lựa chọn sau:
  • Nếu bạn chưa biết đáp án: bạn có quyền đặt câu hỏi cho noodles0428 có dạng 1 i j, trên một dòng.
  • Nếu bạn đã có đáp án: bạn hãy in ra một dãy số có dạng như sau: 2 x với ~x~ là vị trí của một lá bài màu trắng mà bạn đoán, trên một dòng. Kết thúc lượt này, chương trình sẽ ngắt.
• Nếu là lượt của noodles0428, cô ấy sẽ trả lời truy vấn của bạn dưới dạng ~0~ hoặc ~1~.

SAMPLE

Nhiệm vụ của bạn trong bài toán này rất đơn giản: hãy dự đoán kết quả được in ra của đoạn code dưới.

int n; cin >> n;
int res = 0;
for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
        for (int k = j + 1; k <= n; k++) {
            res++;
        }
    }
}
cout << res;

n = int(input())
res = 0
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        for k in range(j + 1, n + 1):
            res += 1
print(res)

INPUT

Dòng đầu tiên gồm số nguyên dương ~t~ (~1 \le t \le 10^4~) là số lượng test.

~t~ dòng tiếp, mỗi dòng gồm một số nguyên dương ~n~ duy nhất (~1 \le n \le 2 \times 10^5~) - input của đề bài.

OUTPUT

~t~ dòng, mỗi dòng xuất ra kết quả được in trong đoạn code dưới.

SAMPLE INPUT

2
1
5

SAMPLE OUTPUT

0
10

Một xâu con của xâu ~S~ được định nghĩa là một đoạn xâu liên tiếp được chọn từ xâu ~S~.

Ví dụ, xâu abc nhận xâu a, b, c, ab, bc, abc làm xâu con.

Một xâu con đặc biệt của xâu ~S~ được định nghĩa là một xâu con mà có ký tự đầu tiên và ký tự cuối cùng giống nhau.

Yêu cầu: Cho xâu ~S~, hãy đếm số lượng xâu con đặc biệt của xâu ~S~.

INPUT

Nhập vào xâu ~S~ (~1 \le |S| \le 10^5~), chỉ bao gồm các ký tự latin viết thường.

OUTPUT

In ra số lượng xâu con đặc biệt của xâu ~S~.

SAMPLE INPUT

abaca

SAMPLE OUTPUT

8

Giải thích: Các xâu con đặc biệt là: a, b, a, c, a, aba, aca, abaca.

Cho 2 số nguyên dương ~n~ và ~s~ (~1 \le n \le 10^4, s \le 9 \times n~). Hãy tìm số nguyên dương nhỏ nhất có ~n~ chữ số (tất cả các chữ số đều có nghĩa, hay không có chữ số ~0~ ở đầu) sao cho tổng các chữ số đúng bằng ~s~.

INPUT

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 10~) là số lượng test.

Với mỗi test, nhập vào một dòng duy nhất chứa hai số nguyên dương ~n~ và ~s~ (~1 \le n \le 10^4, s \le 9 \times n~).

OUTPUT

Với mỗi test, in ra một số nguyên duy nhất là đáp số bài toán trên một dòng.

SAMPLE INPUT

2
2 10
2 12

SAMPLE OUTPUT

19
39

Alice là một người đúng giờ, chính vì thế cô ấy luôn thủ sẵn cho mình một chiếc đồng hồ kỹ thuật số để có thể sát sao thời gian biểu của bản thân nhất có thể.

Hôm nay, dự kiến cô có lịch hẹn với Bob, thế nhưng hiện tại cô lại không ở nhà. Như bao lần khác, cô vẫn mang chiếc đồng hồ kỹ thuật số yêu thích của mình đi, để cô có thể biết chính xác được còn bao lâu nữa cô sẽ phải đi gặp Bob.

"Reng reng", tiếng chuông điện thoại của Alice vang lên đến váng đầu, là Bob gọi điện thoại cho cô. Bob thông báo rằng vì lý do đột xuất, Bob quyết định tới quán cafe để hẹn Alice vào thời điểm gần nhất mà chỉ số giờ và phút trên đồng hồ kỹ thuật của cô đạt hai số giống nhau tính từ thời điểm anh gọi điện thoại cho cô. Tức là, có thể hiện tại anh đã tới rồi, nhưng cũng có thể là chưa tới.

Điều này khiến Alice rất bực mình vì Bob luôn tìm cách làm khó cô. Hãy giúp Alice xác định thời gian Bob đến quán cafe nhé.

Ví dụ:

• Nếu thời điểm mà Bob gọi cho Alice vào lúc 12:15, tức là anh đã tới vào lúc 12:12.
• Nếu thời điểm mà Bob gọi cho Alice vào lúc 10:08, tức là anh sẽ tới vào lúc 10:10.

INPUT

• Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 150~) là số lượng test.
• ~t~ dòng tiếp theo, mỗi dòng là một chuỗi có dạng ~hh:mm~, với ~hh~ (~00 \le hh \le 23~) là giá trị giờ, và ~mm~ (~00 \le hh \le 59~) là giá trị phút tại thời điểm mà Bob gọi cho Alice.

OUTPUT

Với mỗi test, in ra 2 dòng:

• Dòng thứ nhất là giá trị ~0/1~ để xác định liệu Bob đã đến quán cafe chưa/rồi.
• Dòng tiếp theo là xâu có định dạng ~hh:mm~, với ~hh~ là giá trị giờ, và ~mm~ là giá trị phút tại thời điểm mà Bob đã/sẽ tới quán cafe.

Nếu tồn tại nhiều kết quả (hay hai mốc thời gian đều cách đều thời điểm Bob gọi cho Alice), hãy in ra kết quả bất kỳ.

SAMPLE INPUT 1

2
12:15
00:00

SAMPLE OUTPUT 1

1
12:12
1
00:00

SAMPLE INPUT 2

2
10:08
23:23

SAMPLE OUTPUT 2

0
10:10
1
23:23

Hôm nay, noodles0428 học về dãy số Fibonacci. Cô ấy biết rằng đây là một dãy số rất đặc biệt vì nó gắn liền với nhiều ứng dụng thực tế trong đời sống của chúng ta.

Do rất hứng thú với dãy số này, cô ấy đã quyết định nghĩ ra một biến thể của dãy số Fibonacci - đó là dãy số XOR-nacci! Dãy số này như sau:

Gọi ~F_i~ được gọi là số XOR-nacci thứ ~i~.

~F_0 = 0~

~F_1 = 1~.

~F_i = F_{i-1} \oplus F_{i-2}~ với mọi ~i \ge 2~, và ~\oplus~ là phép ~XOR~ bit.

Yêu cầu: Nhiệm vụ của bạn là phải trả lời đúng toàn bộ ~q~ câu hỏi mà cô ấy đưa ra, tức là trả lời đúng tất cả giá trị ~F_n~ với ~n~ là giá trị mà noodles0428 cho.

INPUT

Dòng đầu tiên nhập vào số ~q~ (~1 \le q \le 10^5~) - với ~q~ là số câu hỏi mà noodles0428 đưa ra.

~q~ dòng tiếp theo, mỗi dòng nhập vào một giá trị ~n~ (~1 \le n \le 10^{12}~).

OUTPUT

Bạn cần in ra ~q~ dòng, mỗi dòng là một giá trị ~F_n,~ tương ứng với từng giá trị ~n~ mà noodles0428 cho.

SAMPLE INPUT

3
1
2
3

SAMPLE OUTPUT

1
1
0

Cho hai số nguyên dương ~L~ và ~R~. Hãy đếm số lượng bộ ba ~(i, j, k)~ (~L \le i \le j \le k \le R~) mà tích ~i \times j \times k~ có chữ số tận cùng là ~x~.

INPUT

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 100~) là số lượng test.

Mỗi test gồm ba số nguyên không âm ~L~, ~R~ và ~x~ (~1 \le L \le R \le 10^9~, ~0 \le x \le 9~) trên một dòng.

OUTPUT

Với mỗi test, in ra số cặp số thỏa mãn đề bài trên một dòng.

Vì kết quả có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho ~10^9 + 7~.

SAMPLE INPUT

3
1 5 3
4 19 7
2 5 5

SAMPLE OUTPUT

1
14
3

toberu cần gạch để xây dựng Instafeed của mình. Cậu cần ~n~ viên gạch, viên gạch thứ ~i~ có độ đẹp là ~a_i~. Các viên gạch không được có cùng độ đẹp, vì toberu không muốn xem lại cùng một loại Instareel.

Ngoài ra, cậu có thêm ~m~ yêu cầu dưới dạng ~(i, j)~ (~1 \le i < j \le n~), tức tích độ đẹp của viên gạch thứ ~i~ và ~j~ (hay ~a_i \times a_j~) là số chính phương.

Hãy xây giúp toberu một Instafeed như vậy!

toberu sẽ nhờ bạn xây dựng ~t~ Instafeed với ~n~ và ~m~ riêng biệt. Bạn cần trả lời ~t~ câu hỏi của cậu với dãy ~a~ tương ứng.

INPUT

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 1000~) là số lượng test.

Mỗi test gồm:

• Dòng đầu tiên chứa hai số nguyên không âm ~n~ và ~m~ (~2 \le n \le 10^5~, ~0 \le m \le 10^5~) là số viên gạch và số yêu cầu.
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~(i, j)~ (~1 \le i, j \le n~) mô tả một điều kiện.

Dữ liệu đảm bảo tổng của ~n~ và tổng của ~m~ qua mọi test ~\le 10^5~.

OUTPUT

Với mỗi test, in ra dãy gạch ~a~ bạn tìm được. Bạn cần đảm bảo ~1 \le a_i \le 10^{18}~ (Vì gạch mà đẹp quá thì toberu không xem nổi).

Nếu không có dãy nào thỏa mãn, hoặc chỉ tồn tại một dãy với ít nhất một phần tử ~> 10^{18}~, in ra ~-1~ trên một dòng.

Nếu có nhiều dãy thỏa mãn, in ra dãy bất kỳ.

SAMPLE INPUT

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

SAMPLE OUTPUT

2 8 9
2 8 18 32

Hài lòng với những Instafeed bạn đã xây ở bản dễ, toberu muốn nhờ bạn nốt ~t~ câu hỏi nữa:

Dựng một Instafeed với ~n~ viên gạch bất kỳ, viên gạch thứ ~i~ có độ đẹp là ~a_i~, để thỏa mãn ~m~ yêu cầu dưới dạng ~(i, j)~ (~1 \le i, j \le n~), tức ~a_i~ chia hết cho ~a_j~.

INPUT

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 1000~) là số lượng test.

Mỗi test gồm:

• Dòng đầu tiên chứa hai số nguyên không âm ~n~ và ~m~ (~1 \le n \le 10^5~, ~0 \le m \le 10^5~) là số viên gạch và số yêu cầu.
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~(i, j)~ (~1 \le i, j \le n~) mô tả một yêu cầu.

Dữ liệu đảm bảo tổng của ~n~ và tổng của ~m~ qua mọi test ~\le 10^5~.

OUTPUT

Với mỗi test, in ra dãy gạch ~a~ bạn tìm được. Bạn cần đảm bảo ~1 \le a_i \le 10^{18}~ (Vì gạch mà đẹp quá thì toberu không xem nổi).

Nếu không có dãy nào thỏa mãn, hay chỉ tồn tại dãy sao cho có ít nhất một viên gạch có độ đẹp ~> 10^{18}~, hãy in ra ~-1~.

SAMPLE INPUT

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

SAMPLE OUTPUT

100 50 25 10
10 2 3 5 1

Cho hai số nguyên dương ~a~ và ~b~. Hãy tính ước chung lớn nhất của mọi số nguyên trong đoạn ~[a, b]~.

Bạn cần trả lời ~t~ truy vấn như vậy.

INPUT

Dòng đầu tiên gồm số nguyên dương ~t~ (~1 \le t \le 5000~) là số truy vấn.

Mỗi truy vấn gồm hai số nguyên dương ~a~ và ~b~ (~1 \le a \le b \le 10^{18}~) trên cùng một dòng.

OUTPUT

Với mỗi truy vấn, in ra kết quả trên một dòng.

SAMPLE INPUT

1
2 4

SAMPLE OUTPUT

1

Ta có ước chung lớn nhất của ~2, 3, 4~ là ~1~.

Cho hai dãy số ~a~ có ~n~ phần tử và ~b~ có ~m~ phần tử.

Hãy tìm và in ra một dãy con chung của cả hai dãy (không cần liên tiếp), thỏa mãn các phần tử của dãy con chung là tăng ngặt.

INPUT

Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~ (~1 \le n, m \le 3 \times 10^5~).

Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 10^9~).

Dòng thứ ba gồm ~m~ số nguyên dương ~b_1, b_2, ..., b_m~ (~1 \le b_i \le 10^9~).

OUTPUT

Dòng đầu tiên ghi ra độ dài của dãy con chung.

Dòng thứ hai in ra dãy con chung tìm được. Nếu có nhiều kết quả đúng, in ra kết quả bất kỳ.

Nếu không tồn tại dãy con chung nào, in ra ~0~.

SAMPLE INPUT 1

3 5
2 3 4
3 4 9 6 9

SAMPLE OUTPUT 1

2
3 4

SAMPLE INPUT 2

3 5
1 2 3
4 5 6 7 8

SAMPLE OUTPUT 2

0

Cho một dãy số gồm ~n~ phần tử ~a_1, a_2, ..., a_n~ (với ~1 \le n \le 10^5, |a_i| \le 10^9~) và ~q~ truy vấn (~1 \le q \le 10^5~). Có hai loại truy vấn như sau:

• ~1~ ~l~ ~r~ ~x~: Cộng tất cả các phần tử trong đoạn ~[l, r]~ lên ~x~ đơn vị (với ~|x| \le 10^9~).
• ~2~ ~l~ ~r~ ~x~: Tính ~S = \sum_{i = l}^{r} |a_i - x|~ (với ~|x| \le 10^9~).

INPUT

Dòng đầu tiên nhập vào hai số nguyên ~n~ và ~q~ (~1 \le n, q \le 10^5~)

Dòng tiếp theo nhập vào ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~|a_i| \le 10^9~)

~q~ dòng cuối cùng, mỗi dòng nhập vào một trong hai loại truy vấn ~1~ ~l~ ~r~ ~x~ hoặc ~2~ ~l~ ~r~ ~x~ với ý nghĩa như trên.

OUTPUT

In ra nhiều dòng, mỗi dòng là đáp số của mỗi truy vấn loại ~2~ ~l~ ~r~ ~x~.

SAMPLE INPUT

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

SAMPLE OUTPUT

6 
7
2

Số chính phương là một loại số rất quen thuộc đối với chúng ta. Do đó, duong3982 muốn tổ chức một trò chơi liên quan tới con số này.

Nhắc lại: Một số ~x~ nguyên dương được định nghĩa là số chính phương nếu tồn tại một giá trị ~k~ nguyên dương mà ~k \times k = x~.

Bạn được phát ~n~ viên bi, đánh số từ ~1~ tới ~n~, viên bi thứ ~i~ mang giá trị sức mạnh là ~i~. Bạn được quyền chọn một tập viên bi từ ~n~ viên bi trên, sao cho không tồn tại tích của hai giá trị sức mạnh bất kỳ trong tập viên bi đó có tích là một số chính phương.

Yêu cầu: Hãy đếm số cách chọn tập bi từ ~n~ viên bi trên. Lưu ý, cần tính cả tập rỗng.

INPUT

Nhập vào số nguyên ~n~ (~n \le 5 \times 10^6~).

OUTPUT

In ra đáp số bài toán khi chia lấy dư cho ~10^9 + 7~.

SAMPLE INPUT 1

3

SAMPLE OUTPUT 1

8

SAMPLE INPUT 2

10

SAMPLE OUTPUT 2

384

noodles0428 rất thích uống nước, nhưng cô ấy lại là người cực kỳ cẩn thận (và bị OCD) nên cô ấy không chấp nhận việc số ml nước trong can nước của cô là một số không chia hết cho 10.

Can nước của noodles0428 có ~n~ ml nước. Sức uống của noodles0428 tối đa một ngày là ~X~ ml. Hỏi noodles0428 cần dành ít nhất bao nhiêu ngày uống nước sao cho không một ngày nào can nước của noodles0428 có số nước còn lại không chia hết cho ~10~.

INPUT

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 1000~) là số lượng test.

Với mỗi test, dòng duy nhất nhập vào hai số ~n~ và ~X~ (~n \le 10^{18}~, ~X \le 10^{18}~).

OUTPUT

Với mỗi test, dòng duy nhất in ra số nguyên dương ~a~ là số ngày ít nhất mà noodles0428 cần uống để hết can mà không một ngày nào can nước có số nước không chia hết cho ~10~. Nếu không tồn tại phương án, in ra ~-1~.

SAMPLE INPUT

2
37 10
7 4

SAMPLE OUTPUT

4
-1

Giải thích:

• Test 1: Ngày 1, noodles0428 uống ~7~ ml nước. Ngày thứ 2, 3, 4, noodles0428 uống ~10~ ml nước.
• Test 2: Có thể chứng minh không tồn tại phương án thỏa mãn.

Cho ~n~ hình chữ nhật, hình thứ ~i~ có chiều dài ~a_i~ và chiều rộng ~b_i~.

Bạn được xoay các hình chữ nhật tùy ý. Hãy tìm ra hình chữ nhật có diện tích nhỏ nhất, mà có thể xếp ~n~ hình chữ nhật trên vào hình chữ nhật lớn này, sao cho ~n~ hình chữ nhật đó không chồng lền nhau.

INPUT

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 1000~) là số lượng test.

Mỗi test gồm:

• Dòng đầu tiên chứa hai số nguyên dương ~n~ (~1 \le n \le 3~) là số hình chữ nhật.
• ~n~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~a_i, b_i~ (~1 \le a_i, b_i \le 10^9~) mô tả một hình chữ nhật.

OUTPUT

Với mỗi test, in ra diện tích hình chữ nhật nhỏ nhất tìm được trên một dòng.

SAMPLE INPUT

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

SAMPLE OUTPUT

16
30
68

Đây là một bài toán tương tác.

Wordle là một trò chơi đoán từ đơn giản nhưng đầy thử thách. Người chơi có 6 lượt để đoán một từ tiếng Anh gồm 5 chữ cái. Sau mỗi lần đoán, trò chơi sẽ hiển thị màu sắc để gợi ý:

🟩 Màu xanh lá: chữ cái đúng và đúng vị trí.

🟨 Màu vàng: chữ cái đúng nhưng sai vị trí.

⬜ Màu xám: chữ cái không có trong từ.

Trò chơi được tạo ra vào năm 2021 bởi kỹ sư phần mềm Josh Wardle như một món quà dành tặng bạn gái. Sau đó, Wordle nhanh chóng lan truyền toàn cầu và được The New York Times mua lại vào đầu năm 2022.

Trong bài toán này, bạn được cung cấp ~2000~ từ tiêu chuẩn mà New York Times sử dụng cho trò chơi Wordle gốc. Sau đó, bạn cần đoán đúng từ mà máy chấm đang nắm giữ.

Để bài toán trở nên đơn giản hơn, với mỗi truy vấn, bạn được phép đoán ~8~ lượt.

TƯƠNG TÁC

Đầu tiên, bạn cần nhập ~2000~ xâu từ đầu vào chuẩn, tương ứng với ~2000~ từ sẽ được sử dụng trong trò chơi. Đây là ~2000~ từ có thể là đáp án. Bạn có thể tải 2000 từ tại đây.

Sau đó, bạn cần nhập vào số nguyên dương ~t~ (~1 \le t \le 200~) là số lượng truy vấn.

Với mỗi truy vấn:

• Bạn cần in ra một xâu gồm chính xác ~5~ ký tự in hoa trên một dòng, tương ứng với lượt đoán của bạn. Từ bạn đoán không nhất thiết là một từ trong 2000 từ nói trên.
• Sau đó, bạn cần nhập vào một xâu gồm ~5~ ký tự in hoa từ đầu vào chuẩn trên một dòng, mỗi ký tự thuộc một trong ba loại: ~G~ tương ứng màu xanh lá, ~Y~ tương ứng màu vàng, ~B~ tương ứng màu xám.
• Nếu bạn nhận được một xâu gồm ~5~ chữ ~G~ với không quá ~8~ lượt đoán, chương trình của bạn sẽ cần kết thúc ngay lập tức (nếu đây là test cuối cùng), hoặc cần in ra một xâu gồm ~5~ ký tự in hoa để bắt đầu lượt đoán mới (nếu đây chưa phải test cuối cùng).

Nguyên tắc tô màu của Wordle như sau:

• Gọi ~ans[i]~ là đáp án, và ~guess[i]~ là dự đoán của bạn.
• Đầu tiên, nếu ~ans[i] = guess[i]~, ta tô ô tương ứng màu xanh lá.
• Sau đó, lần lượt từ trái qua phải, nếu ký tự ~guess[i]~ còn trong quỹ ký tự, ta tô ô tương ứng màu vàng.
• Cuối cùng, ta tô các ô chưa được tô màu xám.

Ví dụ, từ cần đoán là APPLE, còn bạn đoán từ ALLEY, ta sẽ nhận được chuỗi màu là GYBYB.

Lưu ý, sau mỗi lần in ra, bạn cần đẩy dữ liệu ra bằng các lệnh flush.

SAMPLE

Bạn được cho ~n~ bóng đèn, các bóng đèn được đánh số từ ~1~ tới ~n~.

Có bốn công tắc với các chức năng như sau:

• Công tắc ~1~: Đảo trạng thái (bật - tắt) tất cả các bóng đèn.
• Công tắc ~2~: Đảo trạng thái các bóng đèn được đánh số chẵn.
• Công tắc ~3~: Đảo trạng thái các bóng đèn được đánh số lẻ.
• Công tắc ~4~: Đảo trạng thái các bóng đèn được đánh số chia ~3~ dư ~1~ (ví dụ: ~1, 4, 7, 10, ...~).

Bạn cần bấm chính xác ~x~ lần, mỗi lần bạn bấm một trong ~4~ nút nói trên.

Xét tất cả ~4^x~ cách bấm, số trạng thái khác nhau của các bóng đèn mà bạn có thể tạo ra là bao nhiêu? Hai trạng thái được gọi là khác nhau, nếu có một bóng đèn mà trạng thái (bật/tắt) ở hai cách là khác nhau.

Vì kết quả có thể rất lớn, hãy in ra kết quả khi chia dư cho ~10^9 + 7~.

INPUT

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 10~) là số bộ test.

Với mỗi bộ test, dòng duy nhất chứa hai số nguyên dương ~n~ và ~x~ (~1 \le n, x \le 10^6~).

OUTPUT

Với mỗi bộ test, in ra kết quả trên một dòng, khi chia lấy dư cho ~10^9 + 7~.

SAMPLE INPUT

3
3 1
2 1
2 2

SAMPLE OUTPUT

4
3
4

Với test ~1~: các trạng thái có là: 000, 010, 101, 011, với ~0~ là tắt, ~1~ là bật.

Với test ~2~: các trạng thái có là: 11, 10, 01.

Với test ~3~: các trạng thái có là: 11, 10, 01, 00.

Cho một chuỗi nhị phân ~S~ độ dài ~n~ (~1 \le n \le 5000~) và một số nguyên ~K~ (~0 \le K \le n~).

Bạn được phép lật tối đa ~K~ bit trong xâu ~S~ (lật bit từ ~0 \rightarrow 1~ hoặc từ ~1 \rightarrow 0~). Bạn cần tìm cách lật bit thỏa mãn điều kiện đề bài sao cho số lần xuất hiện của chuỗi nhị phân con 101 xuất hiện nhiều nhất (có thể chồng lấn).

INPUT

Dòng đầu tiên nhập vào hai số nguyên ~n~ (~1 \le n \le 5000~) và một số nguyên ~K~ (~0 \le K \le n~)

Dòng tiếp theo nhập vào xâu ~S~ nhị phân có độ dài đúng bằng ~n~.

OUTPUT

In ra số nguyên duy nhất là số lần xuất hiện nhiều nhất của chuỗi nhị phân con 101 sau khi lật tối đa ~K~ bit.

SAMPLE INPUT

8 2
10011010

SAMPLE OUTPUT

3

Giải thích: Sau khi lật bit, xâu ~S~ trở thành 10101010

Cho một dãy ~A = \{A_1, A_2, A_3, ..., A_n\}~. Một số ~x~ được gọi là thân thiện với ~A~ nếu tồn tại một bộ chỉ số ~(i_1, i_2, ... i_k)~ thoả mãn

~\left\{\begin{aligned}& i_1 < i_2 < \cdots < i_k \le n,\\& A_{i_1}\;\bigl|\;A_{i_2}\;\bigl|\;\cdots\;\bigl|\;A_{i_k} \;=\; x,\quad\text{với \(\mid\) là phép OR bit.} \end{aligned} \right.~

Yêu cầu: Tìm số nguyên dương nhỏ nhất không thân thiện với ~A~.

INPUT

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 10^5~) là số lượng test.

Mỗi test gồm:

• Dòng đầu tiên là số nguyên ~n~ ~(1 \le n \le 10^5)~
• Dòng tiếp theo là ~n~ số nguyên dương ~A_i~ ~(1 \le A_i \le 10^9)~

Tổng ~n~ của tất cả các testcase không vượt quá ~10^5~.

OUTPUT

In ra ~t~ dòng, tương ứng với số nguyên dương nhỏ nhất không thân thiện với ~A~ với mỗi test.

SAMPLE INPUT

1
3
5 3 2

SAMPLE OUTPUT

1

Cho một số nguyên ~n~, hãy đếm tổng số chữ số ~1~ xuất hiện trong tất cả các số nguyên không âm nhỏ hơn hoặc bằng ~n~.

Input

Dòng đầu tiên gồm số nguyên dương ~t~ ~(1 \le t \le 1000)~ - số lượng testcase:

Trong mỗi testcase có dạng như sau:

• Một dòng duy nhất là số nguyên dương ~n~ ~(1 \le n \le 10^9)~

Output

Một dòng duy nhất là kết quả bài toán

Sample Input

1
13

Sample Output

6

~\text{Nana}~ và ~\text{Zinno}~ được chuẩn bị trước cho một chuỗi ~s~ gồm các kí tự chữ số ~(0 - 9)~ và kí tự ~?~, số kí tự của chuỗi ~s~ luôn là chẵn. Cả hai sẽ chơi trò chơi Number game, luật chơi như sau:

• ~\text{Zinno}~ sẽ là người đi trước
• Trong mỗi lượt, nếu vẫn còn ít nhất một ký tự ~?~ trong ~s~, người chơi sẽ:
  • Chọn một chỉ số ~i~ sao cho ~s_i =~ ~?~ .
  • Thay ký tự ~s_i~ bằng một chữ số từ ~0~ đến ~9~.
• Trò chơi kết thúc khi không còn ký tự ~?~ nào trong ~s~.
• ~\text{Nana}~ thắng nếu khi trò chơi kết thúc, tổng các chữ số ở nửa đầu chuỗi bằng tổng các chữ số ở nửa sau.
• ~\text{Zinno}~ thắng nếu hai tổng đó không bằng nhau.

Giả sử cả hai chơi tối ưu, hỏi ai là người chiến thắng trong cả hai mà ta không cần xem diễn biến cuộc chơi

Input

Dòng đầu tiên là số nguyên dương ~t~ ~(1 \le t \le 10^4)~ ~-~ số lượng testcase

Trong mỗi testcase có dạng như sau:

• Một dòng duy nhất là chuỗi ~s~ đã được chuẩn bị cho ~\text{Zinno}~ và ~\text{Nana}~

Đảm bảo tổng số kí tự các xâu ~s~ của tất cả các testcase luôn không quá ~10^6~

Output

Với mỗi testcase hãy in ra Zinno nếu ~\text{Zinno}~ thắng, ngược lại in ra Nana

Sample Input

2
25??
?3295???

Sample Output

Zinno
Nana

Thử thách cuối cùng rồi, vì vậy bài này đã được duong3982 đưa ra rất ngắn gọn và đơn giản.

Cho hai số nguyên dương ~L~ và ~R~. Ta gọi ~f_i~ là số lượng chữ số phân biệt trong biểu diễn thập phân của ~i~.

Ví dụ: ~f_{322} = 2~, ~f_{321} = 3~, ~f_{30} = 2~.

Hãy đếm xem từ ~L~ đến ~R~ có bao nhiêu số ~i~ (~L \le i \le R~) mà ~i~ chia hết cho ~f_i~.

INPUT

Gồm hai số nguyên dương ~L~ và ~R~ (~1 \le L \le R \le 10^{18}~).

OUTPUT

Số lượng số thỏa mãn.

Vì kết quả có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho ~10^9 + 7~.

SAMPLE INPUT

1 40

SAMPLE OUTPUT

27

Các số thỏa mãn là các số:

1 2 3 4 5 6 7 8 9 10 11 12 14 16 18 20 22 24 26 28 30 32 33 34 36 38 40