Số square-free là số nguyên dương không có ước lớn hơn ~1~ nào là số chính phương cả. Chẳng hạn ~1,10,15,30~ là square-free nhưng ~12,18,25~ thì không. Cho hai số nguyên dương ~L, R~ với ~1 \le L \le R \le 10^7~, yêu cầu đếm số lượng số square-free lớn hơn ~1~, chỉ có ước nguyên tố lấy trong đoạn từ ~L~ đến ~R~.

Input

Dòng đầu tiên gồm số ~t~ là số test với ~1 \le t \le 3.~

Các dòng tiếp theo gồm các cặp ~(L,R)~.

Output

Ứng với mỗi test, cho biết số lượng số square-free thỏa mãn, vì kết quả có thể rất lớn nên lấy modulo ~10^9 + 7.~

Sample input

2
1 4
20 25

Sample output

3
1

Giải thích trong VD1, các số square-free thỏa mãn là: ~2,3,6~, còn trong VD2, chỉ có ~23~ thỏa mãn.

Cho bảng ô vuông ~m \times n~ (gồm ~m~ hàng, ~n~ cột) ban đầu có các ô đèn màu xanh và ~q~ truy vấn dạng sau:

• ~C~ ~i~: đổi màu (xanh sang đỏ và ngược lại) tất cả các ô ở cột thứ i với ~(1 \le i \le n)~.
• ~R~ ~i~: đổi màu (xanh sang đỏ và ngược lại) tất cả các ô ở hàng thứ i với ~(1 \le i \le m)~.

Tính số lượng ô đèn đỏ có trên bảng sau khi kết thúc các truy vấn.

Input Specification

Dòng đầu tiên gồm 2 số nguyên ~m~, ~n~ tương ứng là số hàng và số cột ~(1 \le m, n \le 10^3)~.

Dòng thứ hai gồm 1 số nguyên ~q~ là số lượng các truy vấn ~(1 \le q \le 10^5)~.

Tiếp theo q dòng mô tả các câu truy vấn.

Output Specification

Kết quả 1 số nguyên duy nhất là đáp án của đề bài.

Sample Input

3 4
2
C 1
R 1

Sample Output

5

Trong giải cờ vua của CLB H3.2 mở rộng dành cho K13-K19, có tất cả ~n~ đấu thủ tham gia, thể thức là đấu loại trực tiếp, nghĩa là thí sinh thua sẽ bị loại ngay (giả sử không có trận hòa xảy ra). Ban tổ chức Luna quy định khá lạ rằng: 2 thí sinh chỉ thi đấu được với nhau nếu chênh lệch số trận thắng của họ không quá 1. Tất nhiên với luật này, BTC phải tổ chức giải đấu rất cẩn thận, vì có thể xảy ra tình huống đánh đến một lúc nào đó thì không thể đánh tiếp (do các thí sinh có số trận lệch nhau nhiều hơn 1). Bây giờ giả sử rằng BTC đã sắp xếp giải đấu diễn ra tốt đẹp và cuối cùng, còn lại đúng 1 thí sinh ~X~ đạt giải vô địch, tất cả thí sinh khác đều đã bị loại. Sau khi điều tra thì biết rằng hóa ra ~X~ chính là một quốc tế đại sư ẩn danh của CLB, đẹp trai mà không mê gái, chỉ lo chuyên tâm tu luyện cờ suốt ngày đêm. Câu chuyện về ~X~ còn khá dài dòng nhưng bây giờ BTC Luna có thắc mắc rằng thí sinh ~X~ đó đã thắng được nhiều nhất bao nhiêu trận? Bạn hãy giúp BTC với nhé.

Input

Một số nguyên dương duy nhất ~n~ với ~1 \le n \le 10^{18}.~

Output

Đáp số của bài toán.

Sample input 1

3

Sample output 1

2

Sample input 2

8

Sample output 2

4

Sample input 3

16

Sample output 3

5

Sample input 4

32

Sample output 4

6

Giải thích: trong VD1, ta cho thí sinh 1-2 đấu nhau và 1 thắng, khi đó thí sinh 3 chưa đấu trận nào thì vẫn đánh được với 1 và giả sử thua 1, số trận thắng nhiều nhất của thí sinh 1 sẽ là 2 (các kịch bản khác có thể cho số trận thắng ít hơn 2). Các VD khác làm tương tự.

Trên đường thẳng, cho ~n~ điểm được tô xanh. Mỗi bước được chọn ~k~ điểm liên tiếp và đổi màu tất cả các điểm đó: xanh sang đỏ và ngược lại.

Tính số điểm màu đỏ nhiều nhất có thể thu được.

Input Specification

Dòng duy nhất gồm 2 số nguyên ~n~, ~k~ ~(1 \le k \le n \le 10^{18})~.

Output Specification

Số nguyên duy nhất là đáp án của đề bài.

Sample Input

4 2

Sample Output

4

Bạn Tài và Lộc đang đi coi thầy phong thuỷ để xin quẻ cho một start up công nghệ. Năm trước, hai bạn đã khai trương và xin được một số phong thuỷ là ~n~ nhưng công ty vẫn còn nhiều khó khăn. Lần nay, thầy phong thuỷ phán rằng mỗi số ~n~ là chưa đủ mà hai bạn cần phải chi tiền ra xin thêm vài số nữa về dán thêm vào trong văn phong thì công ty sẽ ăn nên làm ra được. Các số đó, đặt là ~m~, có đặc điểm như sau:

• Đó là các số nguyên dương có giá trị không vượt quá ~n~;
• Là bình phương đúng hoặc lập phương đúng (tức là tồn tại ~x~ nguyên để ~m=x^2~ hoặc ~m=x^3~);
• Mỗi ước nguyên tố (nếu có) của ~m~ thì cũng là ước của ~n~?

Hãy giúp bạn Tài và Lộc tính xem họ cần dán bao nhiêu số theo lời thầy phong thuỷ nhé.

Input

Số nguyên dương ~n~ với ~1 \le n \le 10^{14}.~

Output

Số lượng số đặc biệt cần dán.

Sample input

36

Sample output

7

Giải thích.

Trong ví dụ đã cho, các số thỏa mãn là ~1, 4, 8, 9, 16, 27, 36~. Chú ý rằng số ~1~ vì không có ước nguyên tố nào nên tập ước nguyên tố của nó là tập rỗng, và cũng thoả mãn điều kiện.

Luna và Tina là đôi bạn thân, rất thích chơi các trò bốc sỏi. Luna sẽ đi trước, hai người thay phiên nhau và ai bốc được viên cuối thì thắng. Họ đã trải qua những ngày tháng bốc sỏi cùng nhau. Họ đã thử nhiều luật chơi với số sỏi ban đầu là ~n~ để có những ý tưởng thú vị. Họ có các luật sau đây:

1. Luật 1: mỗi lần chỉ được bốc số sỏi là ~1~ hoặc số nguyên tố.
2. Luật 2: mỗi lần chỉ được bốc số sỏi các luỹ thừa không âm của 2.
3. Luật 3: ở lượt thứ ~k~ thì số sỏi được bốc sẽ là số dương không vượt quá ~k~.
4. Luật 4: ở lượt đầu sẽ không được bốc hết các viên sỏi, còn các lượt sau thì không được bốc số sỏi vượt quá số lượng đã bốc trước đó.

Yêu cầu: với số ~n~ cho trước thì cho biết ai sẽ có chiến lược thắng dựa trên 4 luật chơi đã nêu, giả sử cả hai người đều có cách chơi tối ưu.

Input dòng đầu tiên gồm số ~T~ cho biết số test với ~1 \le T \le 5~, trong ~T~ dòng tiếp theo, mỗi dòng sẽ là một số ~n~ với ~2 \le n \le 10^{18}~.

Output ghi ra ~T~ gồm, mỗi dòng gồm 3 ký tự thuộc ~L, T~ tuỳ theo ai có chiến lược thắng.

Sample input

2
4
5

Sample output

T L L T
L L L L

Cho dãy ký tự ~S~ chứa ~n \le 10^5~ ký tự thuộc tập ~\{H, S, G\}~. Đếm số dãy con ~S'~ của ~S~ sao cho trong ~S'~, số lượng ký tự mỗi loại có tích là lũy thừa của ~2.~

Input

Một dòng duy nhất là chuỗi ký tự, độ dài không quá ~10^5.~

Output

Đáp số của bài toán.

Sample input

HHSSGG

Sample output

4

Giải thích

Các chuỗi con thỏa mãn là: ~HSSG~: số lượng mỗi ký tự là ~1, 2, 1~ nên tích các số lượng ký tự là ~2~, thỏa mãn. Tương tự có ~HSSGG~: tích số lượng ký tự là ~4~; ~HHSSG:~ tích số lượng là ~4~; ~HHSSGG~: tích số lượng là ~8.~

Cho một dãy ~n~ bóng đèn mà mỗi bóng đều được nối với một bộ ~k~ công tắc, các bóng đèn đánh số từ ~1 \to n~ và các công tắc được đánh số từ ~1 \to k~. Trong đó công tắc thứ ~i~ sẽ có thể đổi trạng thái của ~a_i~ bóng liên tiếp tùy ý trong dãy, số ~a_i~ này được gọi là đặc số của công tắc. Ban đầu, tất cả bóng đèn đều tắt và thú vị là nếu chỉ sử dụng riêng một công tắc bất kỳ trong bộ, sau một hoặc nhiều thao tác thích hợp, ta đều có bật tất cả các bóng đèn. Cho biết rằng hệ thống được thiết kế linh hoạt nên các đặc số là đôi một khác nhau giữa các công tắc, và sẽ không có giá trị đặc số nào có tính chất thú vị như trên mà không có trong bộ công tắc.

Bây giờ, giả sử hệ thống công tắc đặc biệt ở trên được nối vào với ~m~ bóng đèn đang tắt. Hỏi cần thao tác ít nhất bao nhiêu lần (cho phép bấm các công tắc khác nhau với số lần tùy ý) để có thể bật tất cả các bóng đèn lên?

Input

Một dòng duy nhất gồm số nguyên ~n, m~, trong đó ~2 \le n \le 10^{12}~ và ~1 \le m \le 10^5.~

Output

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

Sample input 1

4 10

Sample output 1

3

Sample input 2

15 8

Sample output 2

2

Giải thích: Ở VD1, ta có thể c/m rằng hệ thống chỉ có 3 công tắc với các đặc số là ~1, 2, 4~ (đặc số là 3 không thỏa mãn). Khi đó, ta có thể dùng công tắc đặc số là 4 để bật hết bóng đèn ~(1,2,3,4)~ và ~(5,6,7,8)~ của dãy 10 bóng đèn, rồi dùng công tắc đặc số là 2 để bật hai bóng đèn ~(9,10)~ còn lại là được. Khi đó, sẽ tốn tất cả 3 lần thao tác.

Còn ở VD2, ta cũng c/m được rằng hệ thống chỉ có 4 công tắc với các đặc số là ~1, 3, 5, 15~ nên có thể dùng công tắc với đặc số ~3,5~ là đủ.

Vào ngày Tết, do rảnh rỗi không có gì làm nên bạn* Dennis Vũ* đã chơi với một con dế trên bảng ~n \times n~ có gắn sẵn ~n^2~ cái bẫy dế ở trạng thái tắt (mỗi ô một bẫy). Đầu tiên bạn Vũ thả con dế vào ô vuông ở góc dưới bên trái và con dế sẽ bò lên bảng rồi làm chuyển trạng thái những cái bẫy mà nó bò qua theo quy tắc sau:

• Nếu con dế bò vào ô có cái bẫy đang tắt thì nó vẫn an toàn nhưng cái bẫy sẽ âm thầm khởi động lên để chờ nó cho lần bò sau, con dế sẽ tiếp tục bò tiếp về ô phía trước.
• Nếu con dế bò vào ô có cái bẫy đang bật thì nó sẽ bị giật điện, con dế sẽ giật mình và sẽ nhảy sang phải một ô rồi lại bò thẳng tiếp (vẫn cố định hướng từ dưới lên), cái bẫy lúc đó sẽ rơi vào trạng thái tắt.
• Khi đến mép của bảng thì con dế sẽ bị rơi ra ngoài và bị bạn Dennis Vũ bắt lên rồi hành hạ tiếp, tức là lại cho nó bò vào ô đầu tiên ở góc dưới bên trái.

Biết rằng bạn Vũ đã làm như vậy tổng cộng ~m~ lần, hãy xác định xem sau khi kết thúc lần cuối, có bao nhiêu cái bẫy đang được bật lên trên bảng.

Chú ý bên dưới là mô tả cho trạng thái của các cái bẫy trên bảng ~3 \times 3~ sau ~5~ lần bò của con dế (màu đen là cái bẫy được bật lên):

Input

Một dòng duy nhất gồm số nguyên dương ~n,m~ cho biết kích thước bảng và số lần con dế được thả lên, trong đó ~1 \le n \le 10^3~ và ~1 \le m \le 10^9.~

Output

Số bẫy được bật trên bảng.

Sample input 1

3 3

Sample output 1

6

Sample input 2

3 5

Sample output 2

3

Em Phú phá phách vừa mới lớn nên đã bắt đầu tập tành xếp hình. Đây là một trò chơi giải trí lành mạnh rất kích thích phát triển tư duy. Em đã bắt đầu với các quân domino (gồm ~2~ ô vuông ghép lại), rồi tromino (gồm ~3~ ô vuông ghép lại). Hôm nay, em bắt đầu chơi với level cao hơn là tetromino gồm ~4~ ô vuông ghép lại. Chị gái mua cho em nhiều mảnh ghép có dạng tetromino (mỗi mảnh có số lượng tùy ý). Em Phú bèn lấy áo dài của chị để cắt ra thành một hình chữ nhật ~2 \times n~ để xếp lên đó cho dễ. Em đang thắc mắc là có bao nhiêu cách xếp khác nhau với các quân tetromino này để có thể phủ kín được mảnh áo dài của chị mình? Hai cách lát được xem là khác nhau nếu dùng các loại tetromino khác nhau hoặc thứ tự sắp xếp của chúng là khác nhau.

Input

Một dòng duy nhất gồm số nguyên dương ~n~ với ~1 \le n \le 10^{18}~.

Output

Đáp số của bài toán. Vì đáp số có thể rất lớn nên lấy modulo ~10^9+7~.

Sample Input 1

1

Sample Output 1

0

Sample Input 2

2

Sample Output 2

1

Sample Input 3

2022

Sample Output 3

12973685

Giải thích

Ta thấy với ~n=1~ thì nền nhà chỉ có ~2~ ô gạch, không thể lát được, còn với ~n=2~, ta thấy nền nhà có kích thước ~2 \times 2~ nên có một cách duy nhất là dùng hình vuông.

Trong đề Olympic bảng chuyên Tin 2024 vừa qua đã có một bài toán khá thú vị là đếm số tam giác đều trên lưới. Nếu biết công thức là ~C_{n+4}^4~, thí sinh có thể AC nhanh chóng được các sub-task đầu. Tiếp tục ý tưởng đó, mời các bạn thử sức với bài toán sau đây, vẫn trên mô hình lưới tam giác đều:

Cho một tam giác đều mà trên mỗi cạnh của nó có chứa ~n~ điểm chia cạnh đó thành các phần bằng nhau. Nối các điểm chia lại với nhau bởi các đoạn thẳng song song với cạnh tam giác lớn để có một lưới tam giác đều. Các vị trí giao điểm được đánh dấu, được gọi là điểm nút (tính cả đỉnh của tam giác lớn), còn các tam giác chia ra được gọi là tam giác con. Câu hỏi đặt ra bao gồm:

(1) Đếm số hình bình hành có 4 đỉnh là 4 nút của lưới và các cạnh song song với cạnh của tam giác lớn.

(2) Đếm số đường đi từ tam giác đỉnh đến tam giác chính giữa ở dưới cùng, thông qua dãy tam giác kề cạnh, không cho đi lặp lại và không cho đi ngược lên hàng phía trên.

Input. Số nguyên dương ~n~ với ~1 \le n \le 10^6~.

Output. Hai kết quả cần tìm, vì đáp số có thể rất lớn nên lấy số dư khi chia cho ~10^9+7.~

Sample input

3

Sample output

45 6

Xét phép biến đổi ~f~ tác động lên một xâu nhị phân: biến mỗi số ~0, 1~ trong đó thành ~1~, ~01~ cùng lúc. Xuất phát từ ~1~ (coi như ~s_1~), ký hiệu ~s_n~ là xâu sinh ra được sau khi tác động ~f~ lên xâu gốc tất cả ~n~ lần. Cụ thể là

~1 \to 01 \to 101 \to 01101 \to ...~

Chưa dừng lại ở đó, người ta còn ghép các xâu ~s_1, s_2, ...,s_n~ lại với nhau, tạo thành xâu ~t_n.~ Như vậy xâu ~t_4~ sẽ là ~10110101101~ tạo thành từ việc ghép 4 xâu đầu tiên trong dãy ~s_n~ ở trên.

Cho trước số nguyên dương ~n~, câu hỏi đặt ra là:

1) Có bao nhiêu số ~0~ trong xâu ~t_n~?

2) Trong các xâu ~t~ thì số ~0~ thứ ~n~ nằm ở vị trí bao nhiêu?

Input

Số nguyên dương ~n~ duy nhất với ~1 \le n \le 10^{10}~.

Output

Câu trả lời cho hai câu hỏi trên, kết quả có thể ra lớn nên lấy dư khi chia cho ~10^9+7.~

Sample input 1

1

Sample output 1

0 2

Sample input 2

4

Sample output 2

4 10