Cho xâu ~S~, hãy cho biết cần thay đổi ít nhất bao nhiêu kí tự để ~S~ tồn tại xâu con có độ dài lớn hơn ~1~ là xâu đối xứng.

Input

Dòng đầu tiên chứa ~T~ (~1 \leq T \leq 10^5~), số lượng test bạn phải xử lý. ~T~ dòng tiếp theo, mỗi dòng chứa một xâu ~S~ chỉ gồm các ký tự chữ cái Latin in thường.

Tổng số ký tự của ~S~ trong tất cả các testcase không quá ~10^5~.

Output

Gồm ~T~ dòng, mỗi dòng ghi một số nguyên là đáp án của testcase đó. Nếu không thể thay đổi thỏa mãn đề bài thì ghi ~-1~.

Sample Input 1

2
dcbefab
xyzyx

Sample Output 1

1
0

Notes

Ở xâu đầu tiên, ta có thể thay ký tự thứ tư của xâu thành a để được xâu con bafab là xâu con đối xứng của xâu lớn.

Vì bản thân xâu thứ hai đã là xâu đối xứng nên ta không cần thay đổi gì cả.

Hai bạn An và Bình cùng chơi một trò chơi có tên là "nhặt cờ". Trò chơi diễn ra như sau:

• Ban đầu có ~n~ lá cờ. An bắt đầu trước, sau đó tới lượt Bình và 2 người chơi luân phiên nhau cho đến khi trò chơi kết thúc.

• Ở mỗi lượt chơi, người chơi sẽ chọn một số nguyên ~x~ (~1 \leq x \leq m~) và loại bỏ chính xác ~x~ lá cờ ra khỏi trò chơi. Sau lượt chơi của ai mà tất cả ~n~ lá cờ đều bị loại bỏ thì trò chơi kết thúc và người đó sẽ giành chiến thắng.

Với ~n~, ~m~ cho trước, hãy xác định người thắng cuộc của trò chơi nếu cả An và Bình đều chơi tối ưu.

Input

• Dòng đầu chứa số nguyên ~T~ là số truy vấn cần trả lời (số trò chơi mà An và Bình sẽ chơi) (~1 \leq T \leq 10^5~).

• ~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~n,m~ cách nhau bởi dấu cách, là số lá cờ ban đầu và số lá cờ tối đa mỗi người chơi được bốc (~1 \leq n \leq 10^{18}~, ~1 \leq m \leq 10^6~).

Output

Xuất ra ~T~ dòng, mỗi dòng chứa một ký tự duy nhất là kết quả của trò chơi thứ ~i~ (~1 \leq i \leq T~), là "A" nếu An thắng hoặc "B" nếu Bình thắng

Scoring

Sample Input 1

1
5 4

Sample Output 1

B

Sample Input 2

1
5 5

Sample Output 2

A

Notes

• Ở test ~1~, An đi trước và phải loại bỏ một số lá cờ. Sau lượt chơi của An, số lá cờ còn lại chỉ có thể là ~1, 2, 3, 4~ (đều là các số dương ~\leq m~). Khi đó, Bình có thể loại bỏ số lá cờ còn lại trên bàn ngay trong lượt tiếp theo của mình và giành chiến thắng.

• Ở test ~2~, An đi trước, loại bỏ toàn bộ ~5~ lá cờ và giành chiến thắng.

Với một số nguyên dương ~n~, ta gọi nó là số cô đơn nếu ~n~ chỉ có một ước trong đoạn ~[\lceil \frac{n}{10} \rceil,n]~, tức là chỉ tồn tại một số ~x~ thỏa mãn:

• ~\lceil \frac{n}{10} \rceil\le x\le n~

• ~n~ chia hết cho ~x~

Trong đó, ~\lceil x \rceil~ ký hiệu cho số nguyên bé nhất không nhỏ hơn ~x~.

Người ta đem các số cô đơn sắp xếp lại theo thứ tự tăng dần về giá trị: ~1, 11, 13, 17, 19, 23, \ldots~

Yêu cầu: Cho hai số nguyên ~v, k~. Bạn hãy trả lời hai câu hỏi:

• ~v~ là số cô đơn thứ bao nhiêu trong dãy trên?

• Số cô đơn thứ ~k~ trong dãy có giá trị là bao nhiêu?

Dữ liệu đảm bảo ~v~ là số cô đơn giống bạn.

Input

• Dòng đầu tiên chứa số nguyên dương ~T~ ~(1 \le T \le 10^4)~ là số bộ dữ liệu;

• ~T~ dòng tiếp theo, mỗi dòng bao gồm:

  • Hai số nguyên dương ~v, k~ ~(v, k \le 10^{18})~

Output

• In ra ~T~ dòng, mỗi dòng in ra hai số nguyên là câu trả lời cho bộ dữ liệu tương ứng.

Scoring

Sample Input 1

2
13 5
19 3

Sample Output 1

3 19
5 13

Sample Input 2

2
1 1
289 10062006

Sample Output 2

1 1
67 44021273

Notes

Dãy các số cô đơn sắp xếp lại theo thứ tự tăng dần là: ~[1, 11, 13, 17, 19, 23, \ldots]~.

Ở test ví dụ thứ nhất, ~13~ là số cô đơn thứ ba và số cô đơn thứ năm trong dãy là ~19~.

Cho một dãy ~N~ số nguyên dương. Chọn ngẫu nhiên hai chỉ số ~1 \le l, r \le n~. Nếu ~l > r~ thì ta swap hai chỉ số. Trọng số của một đoạn ~[l, r]~ là số giá trị khác nhau trong dãy ~a_l, a_{l + 1}, \ldots, a_r~. Tính Giá trị kì vọng của trọng số nhận được.

Chi tiết về Giá trị kì vọng có thể tìm hiểu ở đây. Ở bài toán này, Giá trị kì vọng có thể hiểu là trung bình cộng của các trọng số nhận được từ tất cả các cách chọn hai chỉ số ~l, r~.

Input

• Dòng đầu tiên gồm số nguyên dương ~N~ ~(1 \le N \le 10^6)~.

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

Output

• Gồm một số nguyên là Giá trị kì vọng của trọng số được viết dưới dạng phân số ~\frac{X}{Y}~ chia lấy dư cho ~10^9 + 7~.

Scoring

Sample Input 1

4
4 2 3 2

Sample Output 1

2

Sample Input 2

7
1 2 8 6 2 8 6

Sample Output 2

918367356

Notes

Ở test ví dụ thứ nhất trên:

• Có ~4~ cặp ~(l, r)~ tương ứng với các đoạn có trọng số bằng ~1~ là (~1, 1~), (~2, 2~), (~3, 3~), (~4, 4~).

• Có ~8~ cặp ~(l, r)~ tương ứng với các đoạn có trọng số bằng ~2~ là (~1, 2~), (~2, 1~), (~2, 3~), (~3, 2~), (~2, 4~), (~4, 2~), (~3, 4~), (~4, 3~).

• Có ~4~ cặp ~(l, r)~ tương ứng với các đoạn có trọng số bằng ~3~ là (~1, 3~), (~3, 1~), (~1, 4~), (~4, 1~).

Từ đó, giá trị kì vọng nhận được là ~\frac{1 \cdot 4 + 2 \cdot 8 + 3 \cdot 4}{16} = 2~.

Ở test ví dụ thứ hai, giá trị kì vọng nhận được là ~\frac{129}{49} \equiv 918367356 \pmod{10^9 + 7}~.

Tân tự nhận mình là người đẹp trai nhất lớp Tin. Nhưng Hiếu không chịu nên đã đố Tân một bài toán đơn giản để coi ai mới là người đẹp trai nhất?

Bài toán như sau: Cho một dãy số gồm ~n~ phần tử và một giá trị ~k~ không đổi. Cho ~q~ truy vấn sau:

— ~1~ ~l~ ~r~ ~x~: Giảm đi một lượng ~x~ trong đoạn ~[l, r]~.

— ~2~ ~l~ ~r~: Đếm số lượng phần tử có giá trị không vượt quá ~k~.

Input

Dữ liệu đầu vào gồm:

• Dòng đầu tiên: ~2~ số ~n, k~ (~1 \le n \leq 5 \times 10^5, 1 \le k \leq 10^9~).

• Dòng thứ hai: dãy số ~a~ có ~n~ phần tử (~1 \le a_i \le 10^9~).

• Dòng thứ ba: số lượng truy vấn ~q~ (~1 \le q \le 5 \times 10^5~).

• ~q~ dòng tiếp theo thuộc ~1~ trong ~2~ loại truy vấn:

  — ~1~ ~l~ ~r~ ~x~: Giảm đi một lượng ~x~ trong đoạn ~[l, r]~ ~(1 \le x \le 10^9)~.

  — ~2~ ~l~ ~r~: Đếm số lượng phần tử trong đoạn ~[l, r]~ có giá trị không vượt quá ~k~.

Output

Dữ liệu đầu ra:

Đáp án cho từng truy vấn loại ~2~ trên từng dòng.

Scoring

Sample Input 1

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

Sample Output 1

3
0
4
8

Notes

Ở truy vấn đầu tiên: ~2~ ~3~ ~7~, trong đoạn vị trí ~[3; 7]~ gồm các số tương ứng là ~[5; 8; 4; 1; 2]~ có ~3~ số thoả ~\le k = 4~ là ~4; 1; 2~ nên đáp án của truy vấn này là ~3~.

Ở truy vấn thứ hai: ~2~ ~2~ ~3~, trong đoạn vị trí ~[2; 3]~ gồm các số tương ứng là ~[10; 5]~ không có số nào thoả ~\le k = 4~ nên đáp án của truy vấn là ~0~.

Trong truy vấn thứ ba: ~1~ ~2~ ~6~ ~4~, ta giảm các số trong đoạn vị trí ~[2; 6]~ xuống ~4~ đơn vị ta có được dãy sau khi thực hiện là ~[3; 6; 1; 4; 0; -3; 2; 1]~.

Ở truy vấn thứ tư: ~2~ ~1~ ~5~, trong đoạn vị trí ~[1; 5]~ gồm các số tương ứng là ~[3; 6; 1; 4; 0]~ có ~4~ số thoả ~\le k = 4~ là ~3; 1; 4; 0~ nên đáp án của truy vấn này là ~4~.

Trong truy vấn thứ năm: ~1~ ~1~ ~4~ ~9~, ta giảm các số trong đoạn vị trí ~[1; 4]~ xuống ~9~ đơn vị ta có được dãy sau khi thực hiện là ~[-6; -3; -8; -5; 0; -3; 2; 1]~.

Ở truy vấn thứ sáu: ~2~ ~1~ ~8~, trong đoạn vị trí ~[1; 8]~ gồm các số tương ứng là ~[-6; -3; -8; -5; 0; -3; 2; 1]~ có ~8~ số thoả ~\le k = 4~ là toàn bộ các số trong dãy nên đáp án của truy vấn này là ~8~.