Robert Duong Hoan là một đại kiện tướng cờ vua của CLB H3.2 với thành tích bất bại trong những lần tham gia hội thao toàn trường. Tuyệt kỹ của anh là: phế hậu tạo sát cục, chiếu hết trong vòng 10 nước, phong tỏa quân bắt tượng, chiếu rút bắt xe, ... đã là nỗi ám ảnh của các cao thủ. Với sự tin tưởng của người hâm mộ, anh đã được giao tổ chức một giải đấu rất đặc sắc nhân dịp kỷ niệm ngày 26/3. Luật chơi như sau:

• Nếu hiện có ~n~ chẵn kỳ thủ thì họ sẽ chia cặp và thi đấu loại trực tiếp, ai thua sẽ bị loại ngay; giải đấu sẽ tiếp tục với ~n/2~ kỳ thủ còn lại.
• Nếu hiện có ~n~ lẻ kỳ thủ thì họ sẽ thi đấu vòng tròn tính điểm (mỗi người đấu với tất cả những người kia), đấu tổng cộng ~n(n-1)/2~ ván (chú ý nếu ~n=1~ thì không cần đấu nữa); xong là kết thúc luôn.

Giả sử rằng không có trận nào hòa. Chẳng hạn: nếu có ~28~ kỳ thủ thì: lượt 1 họ đấu cặp với tổng ~14~ ván, còn ~14~ kỳ thủ; lượt 2 họ lại đấu cặp, thêm ~7~ ván và còn ~7~ kỳ thủ; lượt 3 do còn lẻ kỳ thủ nên họ đấu vòng tròn, thêm ~7(7-1)/2=21~ ván và kết thúc. Tổng cộng có ~14+7+21=42~ ván.

Robert được giao tổ chức đúng ~m~ ván đấu, nhưng bạn ấy thắc mắc rằng số kỳ thủ ít nhất cần mời để có số trận đấu như thế là bao nhiêu. Bạn hãy giúp bạn ấy với nhé.

Input

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

Output

Số kỳ thủ ít nhất cần mời. Nếu không tồn tại cách mời thi in ra ~-1.~

Sample input 1

42

Sample output 1

28

Sample input 2

1

Sample output 2

2

Cho số nguyên dương ~n~ và có hai bạn ~A, B~ sẽ chơi một trong hai trò chơi sau đây (~A~ luôn đi trước).

• Luật 1: ở mỗi lượt, người chơi sẽ trừ vào số hiện tại ước dương của nó mà ước đó khác ~1~ và khác chính số đó, cụ thể là nếu có ~x~ thì có thể chọn một trong các ước của nó là ~d~ mà ~1 < d < x~ và thay ~x \to x-d.~

• Luật 2: ban đầu, tất cả các ước của ~n~ sẽ được viết ra và ở lượt đầu tiên, ~A~ bắt buộc phải xóa số ~n.~ Ở mỗi lượt tiếp theo, người chơi sẽ xóa ước hoặc bội của số mà người kia xóa ở lượt đi trước đó.

Trong mỗi luật chơi, ai đến lượt đi của mình mà không thực hiện được thì thua cuộc. Vấn đề đặt ra là xác định người có chiến lược thắng, trong đó giả sử 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, trong đó ~1 \le T \le 10.~ Mỗi dòng tiếp theo là giá trị của ~n~ trong test, trong đó ~1 \le n \le 10^9.~

Output

Với mỗi test, cho biết ai là người có chiến lược thắng. In ra ~A, A~ hoặc ~A, B~ hoặc ~B, A~ hoặc ~B, B~ một cách thích hợp.

Sample input

2
1
6

Sample output

B A
A B

Giải thích

Trong Ví dụ 1, với ~n=1~ thì theo luật ~1~ thì ~A~ không đi được lần nào; còn theo luật ~2~, người ~A~ sẽ xóa số ~1~ và ~B~ sẽ không còn gì để chơi. Trong Ví dụ 2, với ~n=6~ thì ở luật ~1~, người ~A~ có thể trừ ~n~ cho ~3~, khi đó còn lại ~3~ và ~B~ gặp số ~3~ thì thua ngay; còn ở luật ~2~, có các ước ~1,2,3,6~ ban đầu ~A~ đã xóa số ~6~ thì ~B~ xóa ~3~, đến lượt ~A~ chỉ có thể xóa ~1~ và tiếp theo ~B~ xóa ~2~ thì thắng luôn.

Trong ngày cuối cùng trước khi học kỳ mới bắt đầu, CLB H3.2 có tổ chức một Vũ hội, trong đó các thành viên sẽ múa hát xuyên màn đêm. Để buổi Vũ hội thêm rực rỡ, Ban tổ chức đã lắp thêm ~n~ bóng đèn trang trí vào khắp phòng, và các bóng đèn được đánh số từ ~1~ đến ~n~. Có tất cả ~6~ công tắc với các tính năng như sau:

• Công tắc 1: thay đổi trạng thái tất cả các bóng đèn (từ bật thành tắt, tắt thành bật).
• Công tắc 2: cũng thay đổi trạng thái nhưng chỉ với các bóng có số thứ tự chẵn.
• Công tắc 3: cũng thay đổi trạng thái với các bóng có số thứ tự lẻ.
• Công tắc 4: cũng thay đổi trạng thái với các bóng có số thứ tự chia hết cho ~3~.
• Công tắc 5: cũng thay đổi trạng thái với các bóng có số thứ tự chia ~3~ dư ~1~.
• Công tắc 6: cũng thay đổi trạng thái với các bóng có số thứ tự chia ~3~ dư ~2~.

Ban đầu, tất cả bóng đèn đều bật. Trong buổi tiệc, DJ Banana sẽ lo việc điều phối âm nhạc và bật tắt các công tắc để không khí thêm phần mờ ảo. Đến cuối buổi tiệc, Banana mắt lim dim đếm được có ~m~ bóng đèn còn bật (các bóng còn lại chưa rõ bật hay tắt) và đếm được rằng đã bấm công tắc tổng cộng ~c~ lần. Hỏi có thể có bao nhiêu khả năng xảy ra đối với ~n~ bóng đèn của đêm Vũ hội?

Input

Một dòng duy nhất gồm số bóng đèn ~n~ với ~1 \le n \le 10^5~, số bóng đèn còn bật mà Banana đã thấy được là ~m~ với ~0 \le m \le n~ và tổng số lần ấn công tắc ~c~ với ~0 \le c \le 10^9~.

Dòng tiếp theo cho biết số thứ tự của các bóng đèn còn bật mà Ban thấy được (chú ý một lần nữa rằng các bóng còn lại thì không rõ là bật hay tắt).

Output

Số tất cả trạng thái có thể có thể (kết quả này vẫn tính được trong kiểu Int64).

Sample input 1:

4 2 1
1 2

Sample output 1:

1

Sample input 2:

8 2 100
1 5

Sample output 2:

4

Giải thích: trong VD1, ta thấy ở cuối cùng còn bóng đèn ~1,2~ còn bật, các bóng ~3,4~ chưa rõ trạng thái, ngoài ra được nhấn công tắc ~1~ lần. Như thế thì có thể nhấn công tắc ~4~ một lần và bóng có STT chia hết cho ~3~ sẽ tắt, lúc đó các bóng còn bật là ~1,2,4~, dễ thấy không còn trạng thái nào khác có thể thu được. Trong VD2, ta có một trong các cách là bật tắt công tắc 1 tất cả ~100~ lần, khi đó cuối cùng tất cả bóng đèn đều bật (nên rõ ràng trong đó có bóng ~1,5~ cũng còn bật).

Trong truyền thuyết của CLB H3.2 viết, những con cá hồi có thể vượt qua nhiều vũ môn để trở thành InfinitySalmon. Mỗi vũ môn là một chặng đường phấn đấu trong cuộc đời của con cá hồi và được đại diện bởi một con số nguyên dương. Như vậy các vũ môn sẽ tạo thành một dãy gồm ~n~ số nguyên dương tăng ngặt và vũ môn cuối cùng có giá trị không vượt quá ~m~. Con cá hồi trong câu chuyện hôm nay khá đặc biệt, nó thích trong lần thứ ~i~ (với ~1 \le i \le n~) thì giá trị vũ môn nó vượt qua sẽ có cùng số dư với ~i^2~ khi chia cho ~k~. Bạn hãy giúp con cá hồi đếm xem có bao nhiêu cách để trở thành InfinitySalmon nhé, do kết quả có thể rất lớn nên lấy modulo ~10^9+7.~

Input

Một dòng duy nhất gồm ba số nguyên dương ~n,m,k~ trong đó ~1 \le n \le 10^5~, ~1 \le m \le 10^9~, ~1 \le k \le 10^6~.

Output

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

Sample input 1.

2 4 2

Sample output 1.

3

Sample input 2.

12 2021 12

Sample output 2.

608212426

Giải thích. Trong VD1, con cá hồi có thể nhảy với các cách là: ~1 \to 2~ hoặc ~1 \to 4~ hoặc ~3 \to 4~.

Mít và Xoài là các SV xuất sắc của thầy Luna. Sau khi dạy xong một tuyệt chiêu về phép đếm trong lập trình, thầy đã ra một bài rất tâm đắc cho Mít và Xoài làm. Hai bạn được cho bảng ô vuông kích thước ~n \times n~, mỗi ô được tô bởi một trong ba màu: xanh - đỏ - vàng sao cho không có hàng nào và không có cột nào được tô tất cả các ô bởi màu đỏ. Đánh số các hàng, cột theo thứ tự từ trái sang phải và dưới lên trên. Ban đầu có sẵn ~k~ ô được thầy Luna tô màu xanh hoặc vàng trước, cho biết danh sách tọa độ của chúng là thứ tự của hàng, cột của ô được tô. Nhiệm vụ của Mít và Xoài là đếm xem có tất cả bao nhiêu cách tô thỏa mãn điều kiện đề bài và kết quả có thể rất lớn nên lấy modulo ~10^9+7.~ Đã nhiều ngày nhưng các bạn vẫn chưa đếm xong, bạn có thể giúp hai bạn ấy được không?

Input

Dòng đầu tiên gồm hai số nguyên dương ~n,k~ trong đó ~1 \le n \le 10~ và ~0 \le k \le \min \{ n^2, 10 \}~. Các dòng tiếp theo mô tả tọa độ của các ô được tô màu trước với dạng ~x\, y \, z~ trong đó ~x,y~ là chỉ số hàng, cột, còn ~z~ là màu: ~z=1~ là xanh, ~z=2~ là vàng.

Output

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

Sample input

2 0

Sample output 1

56

Sample input 2

3 2
1 1 2
2 3 1

Sample output 2

2034