Dãy số Fibonacci là một dãy số quen thuộc với tất cả các bạn. Dãy số này có công thức truy hồi như sau:

• ~f_0~ ~=~ ~0~.
• ~f_1~ ~=~ ~1~.
• ~f_i~ ~=~ ~f_{i - 1} + f_{i - 2}~ với ~i \ge 2~.

Yêu cầu: Cho một số nguyên dương ~x~. Hãy tìm ~i~ sao cho ~f_i = x~. Nếu có nhiều số ~i~ thỏa mãn, hãy in ra ~i~ lớn nhất. Nếu không tồn tại ~i~ thỏa mãn, hãy in ra ~-1~.

INPUT

• Dòng đầu chứa số nguyên dương ~T~ (~1 \le T \le 1000~) là số bộ test.
• ~T~ dòng sau, mỗi dòng chứa một số nguyên dương ~x~ (~1 \le x \le 10^{12}~).

OUTPUT

~T~ dòng, mỗi dòng là số ~i~ sao cho ~f_i = x~. Nếu không tồn tại ~i~ thỏa mãn, in ra ~-1~.

SAMPLE INPUT

2
2
3

SAMPLE OUTPUT

3
4

duong3982 là một người rất thích ăn kem vanilla. Hiện tại, nhà anh ấy đang có sẵn ~S~ hộp kem vanilla. Mỗi ngày, anh ấy mua ~x~ hộp kem rồi sau đó ăn ~y~ hộp. Hỏi đến ngày thứ bao nhiêu, số hộp kem anh ấy có không đủ để đáp ứng nhu cầu ăn của anh ấy nữa? Biết rằng, hiện tại trong tủ lạnh của anh ấy đang có sẵn ~S~ hộp kem vanilla.

INPUT

• Dòng đầu tiên ghi 3 số nguyên dương ~S, x, y~ ~(1 \le S, x, y \le 10^{18})~

OUTPUT

• Dòng duy nhất in ra đáp số đề bài. Nếu không tồn tại đáp án thỏa mãn, hãy in ra ~-1~.

SAMPLE INPUT 1

5 3 2

SAMPLE OUTPUT 1

-1

SAMPLE INPUT 2

10 4 5

SAMPLE OUTPUT 2

11

ghuy4g hiện nay đang học lớp một. Hôm nay, em ấy có bài tập về nhà như sau:

Cho số ~x~ gồm một hoặc hai chữ số. Hãy viết cách đọc số ~x~ trên bằng tiếng Việt theo chuẩn SGK Toán lớp 1.

Vì hôm nay ghuy4g không nghe giảng nên mãi chưa thể giải bài tập trên. Hãy giúp ghuy4g nhé!

INPUT

• Dòng đầu tiên ghi ~t~ là số câu hỏi (~1 \le t \le 10^6~)
• ~t~ dòng tiếp theo, mỗi dòng là một số ~x~ (~1 \le x \le 99~)

OUTPUT

• In ra đáp án của từng câu hỏi trên.

SAMPLE INPUT

2
20
42

SAMPLE OUTPUT

hai muoi
bon muoi hai

Cho hai số nguyên dương ~A~ và ~B~. Hãy tìm chữ số tận cùng của ~A^B~.

INPUT

• Dòng đầu tiên ghi ~t~ là số câu hỏi (~1 \le t \le 10^6~).
• ~t~ dòng tiếp theo, mỗi dòng là hai số nguyên dương ~A~ và ~B~ (~1 \le A, B \le 10^{18}~).

OUTPUT

• Để giảm kích thước đầu ra, hãy in ra tổng của các kết quả qua tất cả truy vấn.

SAMPLE INPUT

2
2 3
3 2

SAMPLE OUTPUT

17

Ta có ~2^3~ có chữ số tận cùng là ~8~, ~3^2~ có chữ số tận cùng là ~9~, vì vậy ta in ra ~8 + 9 = 17~.

Lưu ý: 3 phiên bản của bài này là 3 bài "giống mà khác - khác mà giống". Hãy đọc thật kỹ đề bài nhé!

Búp bê Matryoshka là một loại búp bê nổi tiếng ở Nga. noodles0428 là một người rất thích chơi loại búp bê như thế, nên cô ấy quyết định mua một lô về chơi.

Dòng búp bê này có tính chất rất đặc biệt. Hai búp bê có thể gộp lại với nhau nếu búp bê nằm ngoài lớn hơn ít nhất gấp ~X~ lần so với búp bê nằm trong.

Do cô ấy hay lòng vòng, noodles0428 đang đúng trước gian hàng búp bê và không biết phải mua thế nào để chọn đúng ~K~ con búp bê, mỗi con búp bê có kích thước lớn nhất là ~K~, và không tồn tại cặp búp bê nào có thể gộp lại vào nhau. Hỏi, có bao nhiêu cách mua búp bê thỏa mãn bài toán của cô ấy?

Hai cách mua được gọi là khác nhau, khi tồn tại một số ~i~ ~(1 \le i \le K)~, sao cho búp bê thứ ~i~ được mua ở cách này, khác búp bê thứ ~i~ được mua ở cách kia.

INPUT

• Dòng duy nhất ghi hai số nguyên dương ~K, X~ (~2 \le K \le 8~, ~1 \le X \le 8~).

OUTPUT

• Dòng duy nhất là đáp số của bài toán.

SAMPLE INPUT

3 3

SAMPLE OUTPUT

15

Lưu ý: 3 phiên bản của bài này là 3 bài "giống mà khác - khác mà giống". Hãy đọc thật kỹ đề bài nhé!

Búp bê Matryoshka là một loại búp bê nổi tiếng ở Nga. noodles0428 là một người rất thích chơi loại búp bê như thế, nên cô ấy quyết định mua một lô về chơi.

Dòng búp bê này có tính chất rất đặc biệt. Hai búp bê có thể gộp lại với nhau nếu búp bê nằm ngoài lớn hơn ít nhất gấp ~X~ lần so với búp bê nằm trong.

Do cô ấy hay lòng vòng, noodles0428 đang đúng trước gian hàng búp bê và không biết phải mua thế nào để chọn đúng ~K~ con búp bê, mỗi con búp bê có kích thước lớn nhất là ~K~, và không tồn tại cặp búp bê nào có thể gộp lại vào nhau. Hỏi, có bao nhiêu cách mua búp bê thỏa mãn bài toán của cô ấy?

Hai cách mua được gọi là khác nhau, khi tồn tại một số ~i~ ~(1 \le i \le K)~, sao cho số lượng búp bê kích thước ~i~ được mua ở cách này, khác số lượng búp bê kích thước ~i~ được mua ở cách kia.

INPUT

• Dòng duy nhất ghi hai số nguyên dương ~K, X~ (~2 \le K \le 200~, ~1 \le X \le 5~).

OUTPUT

• Dòng duy nhất là đáp số của bài toán khi chia dư cho ~10^9+7~

SAMPLE INPUT

3 2

SAMPLE OUTPUT

5

Có ~5~ cách mua là:

• ~1, 1, 1~
• ~2, 2, 2~
• ~2, 2, 3~
• ~2, 3, 3~
• ~3, 3, 3~

Lưu ý: 3 phiên bản của bài này là 3 bài "giống mà khác - khác mà giống". Hãy đọc thật kỹ đề bài nhé!

Búp bê Matryoshka là một loại búp bê nổi tiếng ở Nga. noodles0428 là một người rất thích chơi loại búp bê như thế, nên cô ấy quyết định mua một lô về chơi.

Dòng búp bê này có tính chất rất đặc biệt. Hai búp bê có thể gộp lại với nhau nếu búp bê nằm ngoài lớn hơn ít nhất gấp ~X~ lần so với búp bê nằm trong.

Do cô ấy hay lòng vòng, noodles0428 đang đúng trước gian hàng búp bê và không biết phải mua thế nào để chọn đúng ~K~ con búp bê, mỗi con búp bê có kích thước lớn nhất là ~K~, và không tồn tại cặp búp bê nào có thể gộp lại vào nhau. Hỏi, có bao nhiêu cách mua búp bê thỏa mãn bài toán của cô ấy?

Hai cách mua được gọi là khác nhau, khi tồn tại một số ~i~ ~(1 \le i \le K)~, sao cho số lượng búp bê kích thước ~i~ được mua ở cách này, khác số lượng búp bê kích thước ~i~ được mua ở cách kia.

INPUT

• Dòng duy nhất ghi hai số nguyên dương ~K, X~ (~2 \le K \le 10^5~, ~1 \le X \le 10^5~).

OUTPUT

• Dòng duy nhất là đáp số của bài toán khi chia dư cho ~10^9+7~

SAMPLE INPUT

3 2

SAMPLE OUTPUT

5

Có ~5~ cách mua là:

• ~1, 1, 1~
• ~2, 2, 2~
• ~2, 2, 3~
• ~2, 3, 3~
• ~3, 3, 3~

duong3982 được noodles0428 tặng một xâu ký tự ~S~, chỉ gồm các ký tự tiếng Anh in thường, và ký tự ?.

Một xâu ~s~ được gọi là đẹp khi và chỉ khi điều kiện sau thỏa mãn:

Với mọi xâu con liên tiếp độ dài lớn hơn hoặc bằng ~2~ của ~s~, không có ký tự nào có số lần xuất hiện nhiều hơn ~\frac{|s|}{2}~, với ~|s|~ là số ký tự của xâu ~s~.

Ví dụ:

• Xâu wrongans là xâu đẹp.
• Xâu accepted không phải xâu đẹp, do có xâu con acc có ký tự ~c~ xuất hiện ~2 > \frac{3}{2}~ lần.

Sau khi được noodles0428 tặng xâu ~S~, duong3982 tự hỏi, có bao nhiêu cách thay dấu ? thành các ký tự tiếng Anh in thường, thỏa mãn ~S~ là xâu đẹp?

Vì kết quả có thể rất lớn, hãy in ra kết quả modulo ~20032024~.

INPUT

• Dòng duy nhất chứa xâu ~s~ (độ dài không vượt quá ~5000~).

OUTPUT

• Dòng duy nhất là đáp số của bài toán, khi chia dư cho ~20032024~.

SAMPLE INPUT 1

a?m

SAMPLE OUTPUT 1

24

SAMPLE INPUT 2

a?a

SAMPLE OUTPUT 2

0

duong3982 có một dãy số ~A~, ban đầu rỗng. duong3982 lần lượt thực hiện ~n~ thao tác như sau:

• Mỗi thao tác bao gồm hai số nguyên dương ~L~ và ~R~.
• duong3982 sẽ thêm vào dãy ~A~ các phần tử ~L~, ~L + 1~, ..., ~R~ lần lượt vào dãy ~A~.

Sau khi thực hiện ~n~ thao tác, duong3982 sẽ nhận được một dãy ~A~ độ dài ~\sum R_i - L_i + 1~. duong3982 tự hỏi, độ dài của dãy con tăng ngặt dài nhất (không nhất thiết liên tiếp) của dãy này là bao nhiêu?

Yêu cầu: Hãy giúp duong3982 trả lời câu hỏi trên.

INPUT

Dòng đầu tiên chứa số nguyên dương ~n~ (~1 \le n \le 10^5~), là số thao tác duong3982 thực hiện.

~n~ dòng sau, mỗi dòng gồm hai số nguyên dương ~L~ và ~R~ (~1 \le L \le R \le 10^9~) mô tả một thao tác.

OUTPUT

Độ dài của dãy con tăng ngặt dài nhất.

SAMPLE INPUT

3
1 2
10 12
6 9

SAMPLE OUTPUT

6

Dãy ~A~ sau ~n~ thao tác là ~[1, 2, 10, 11, 12, 6, 7, 8, 9]~, có độ dài dãy con tăng dài nhất là ~6~ (dãy ~1, 2, 6, 7, 8, 9~).