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

Mạnh SadBoy là một chàng trai nổi tiếng trong câu lạc bộ lập trình Programming Lab của IUH. Anh ta đam mê lập trình từ nhỏ và ước mơ trở thành một Dev Game.

Nhân ngày 14/2 này, Mạnh đã viết ra một con game tặng cho H để cô ấy có thể chơi game này giải trí lúc không có Mạnh bên cạnh.

Game khá đơn giản, trong game người chơi phải điều khiển nhân vật của mình đi farm lính (hạ gục lính) để có tiền, sau khi có tiền nhân vật sẽ có thể mua các thuốc tăng sức mạnh (sức mạnh đầu game của nhân vật là ~0~). Và khi có chỉ số sức mạnh đúng bằng ~N~ thì người chơi có thể hạ gục được trùm cuối và qua màn tiếp theo. Khi hạ gục được ~1~ lính thì người chơi sẽ có được ~1~ vàng và trong cửa hàng có bán ~4~ loại thuốc tăng cường sức mạnh như sau:

1. Loại ~1~: sẽ tăng sức mạnh hiện tại lên ~2~ lần và có giá là ~A~ vàng.
2. Loại ~2~: sẽ tăng sức mạnh hiện tại lên ~3~ lần và có giá là ~B~ vàng.
3. Loại ~3~: sẽ tăng sức mạnh hiện tại lên ~5~ lần và có giá là ~C~ vàng.
4. Loại ~4~: sẽ tăng thêm hoặc giảm bớt ~1~ sức mạnh của nhân vật và có giá là ~D~ vàng.

Để đảm bảo game không có bị bug gì và đảm bảo H không hack được game của Mạnh code ra, nên Mạnh đã nhờ bạn chơi thử game này trước và yêu cầu bạn mỗi lần chơi bạn hãy cho anh ấy biết số lính tối thiểu mà bạn cần phải đi farm để có thể vượt qua màn chơi tương ứng nhé.

Input

Dòng đầu tiên chứa sớ nguyên ~T~ là số màn chơi Mạnh cần nhờ bạn chơi thử (~ 1 \leq T \leq 10 ~).

~T~ dòng tiếp theo, mỗi dòng sẽ chứa ~4~ số nguyên ~N, A, B, C, D~ tương ứng (~1 \leq N \leq 10^{18}, 1 \leq A, B, C, D \leq 10^9~).

Output

Với mỗi màn chơi, bạn hãy in ra số lính tối thiểu cần phải hạ gục để có đủ lượng vàng nâng cấp sức mạnh và vượt qua màn game.

Sample Input

4
15 10 3 2 1
15 2 2 2 2
202 40 2 1 9
20240219 6 8 6 8

Sample Output

5
6
42
132

Giải thích

Ở trường hợp 1, cách để nhân vật có sức mạnh ~15~ như sau:

1. Đầu tiên, nhân vật sức mạnh là ~0~
2. Tăng sức mạnh của nhân vật lên ~1~ với ~1~ đồng khi thuốc loại ~4~
3. Tăng sức mạnh của nhân vật lên ~2~ với ~1~ đồng khi thuốc loại ~4~
4. Tăng sức mạnh của nhân vật lên ~3~ với ~1~ đồng khi thuốc loại ~4~
5. Tăng sức mạnh của nhân vật lên ~15~ với ~2~ đồng khi thuốc loại ~3~

Như vậy cần có ít nhất là ~5~ vàng.

SubTask

• SubTask 1: 40 điểm với testcase có ~N \leq 10~
• SubTask 2: 60 điểm với testcase có ~N \leq 10^{18}~

CodeCamp là hoạt động thường niên của IUH hằng năm dành cho các bạn trong đội tuyển Olympic Tin Học của trường. Trong các chuyến đi CodeCamp, thầy Tình sẽ dắt các bạn trong đội tuyển đến một vùng đất mới và riêng biệt để các bạn trong đội tuyển có thể tập trung toàn bộ thời gian của mình chỉ để học code và luyện code cùng nhau.

Năm 2023, đội tuyển đã được thầy Tình cho đi CodeCamp ở Đà Lạt. Trước khi xuất phát chuyến đi, thầy Tình yêu cầu ~N~ bạn thành viên trong đội tuyển chọn cho mình một con số yêu thích, và thầy Tình sẽ cho ~2~ bạn có cùng độ tương thích về con số yêu thích sẽ ngủ cùng 1 phòng và những ai không có độ tương thích với ai cả thì sẽ ngủ ở phòng lớn.

Cụ thể, ~N~ thành viên trong đội tuyển mỗi bạn sẽ có con số yêu thích là ~A_i~ (~ 1 \leq i \leq N ~). ~2~ bạn có chỉ số ~i~ và ~j~ sẽ có cùng độ tương thích khi và chỉ khi:

• ~1 \leq i < j \leq N~
• ~A_i + A_j = 2 * lcm(A_i, A_j)~ với ~lcm(A_i, A_j)~ là bội chung nhỏ nhất của ~A_i~ và ~A_j~

Là một trong các thành viên của đội tuyển Olympic Tin Học IUH, bạn hãy giúp thầy Tình đếm trong ~N~ thành viên sẽ có bao nhiêu cặp có cùng độ tương thích nhé.

Input

Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^5~) là số lượng thành viên trong đội tuyển.

Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, A_3,... A_N~ (~1 \leq A_i \leq 10^9~) tương ứng với con số yêu thích của thành viên thứ ~i~.

Output

Xuất ra một số nguyên duy nhất là số lượng cặp các bạn sinh viên có cùng độ tương thích.

Sample Input

6
2 3 3 5 7 19022024

Sample Output

1

SubTask

• SubTask 1 (50 điểm): với ~N \leq 100~ và ~A_i \leq 100~.
• SubTask 2 (50 điểm): không có giới hạn gì thêm.

Ngoài Mạnh SadBoy, trong câu lạc bộ lập trình* Programming Lab* của IUH còn có một thành viên đặc biệt khác anh ấy tên là BanQ. BanQ là một người năng động và hài hước, anh ấy có đam mê đặc biệt với toán học và lập trình. Do là một con người hướng ngoại nên năm mới này BanQ được rất nhiều lì xì từ cô chú trong gia đình thế nhưng không phải với bao lì xì nào BanQ cũng cảm thấy hạnh phúc.

Trong các bao lì xì của BanQ, mỗi bao sẽ chứa ~x~ tiền (~1 \leq x \leq 10^6~). Chỉ số hạnh phúc của BanQ là số lượng cặp nguyên tố cùng nhau của các giá trị tiền trong các bao lì xì mà BanQ có.

Cụ thể, BanQ sẽ có ~q~ thao tác tác động đến số lượng bao lì xì của mình trong năm mới. Với mỗi thao tác sẽ thuộc ~1~ trong ~2~ loại sau:

• Loại ~1~: BanQ nhận được một bao lì xì có giá trị là ~x~ tiền (~1 \leq x \leq 10^6~).
• Loại ~2~: BanQ sẽ lấy ra một bao lì xì có giá trị là ~x~ tiền (~1 \leq x \leq 10^6~) để lì xì cho các em nhỏ.

Với mỗi thao tác, bạn hãy cho biết chỉ số hạnh phúc của BanQ hiện tại là bao nhiêu.

Input

Dòng đầu tiên chứa số nguyên ~q~ (~1 \leq q \leq 10^5~) là số lượng thao tác tác động đến số lượng bao lì xì của BanQ.

~q~ dòng tiếp theo mỗi dòng sẽ chứa ~2~ số nguyên ~t~ và ~x~ (~1 \leq t \leq 2, 1 \leq x \leq 10^6~) là loại thao tác và số tiền của bao lì xì tương ứng.

Đảm bảo với thao tác loại ~2~ BanQ vẫn đang có bao lì xì tương ứng.

Output

Với mỗi thao tác, bạn hãy in ra màn hình chỉ số hạnh phúc hiện tại của BanQ.

Sample Input

6
1 11
1 31
2 11
1 2024
1 1902
2 31

Sample Output

0
1
0
1
2
0

SubTask

• SubTask 1: ~ 30\% ~ số test, với ~q \leq 10^3~.
• SubTask 2: ~70\%~ số test còn lại, không có ràng buộc gì thêm.

Đầu Xuân năm mới, thầy Lữ tặng các bạn tham gia contest "Khai Xuân 2024" này một vài chuỗi lộc để lấy may mắn cho năm mới. Với chuỗi lộc này, các bạn cần phải thực hiện một vài thao tác biến đổi để nhận được phần quà từ thầy Lữ.

Chuỗi lộc chỉ bao gồm hai loại kí tự ~0~ và ~1~. Các bạn có thể thực hiện các thao tác xóa kí tự ~0~ trên chuỗi lộc, để nhận được quà từ thầy Lữ chuỗi lộc của bạn phải là chuỗi chứa ít nhất một kí tự ~1~ và các kí tự ~1~ trên chuỗi này phải đứng cạnh nhau.

Với mỗi chuỗi lộc mà thầy Lữ cho bạn, bạn hãy cho biết cần thực hiện ít nhất bao nhiêu thao tác xóa kí tự ~0~ để có thể đem chuỗi lộc này đổi quà từ thầy Lữ nhé. Nếu không có cách biến đổi nào để nhận được quà từ thầy Lữ bạn hay in ra ~-1~.

Input

Dòng đầu tiên chứa số nguyên ~T~ (~1 \leq T \leq 1000~) là số chuỗi lộc mà thầy Lữ cho bạn.

~T~ dòng tiếp theo, mỗi dòng sẽ chứa một chuỗi lộc ~S~ gồm ~N~ kí tự (~1 \leq N \leq 100~).

Output

Với mỗi chuỗi lộc, bạn hãy cho biết cần ít nhất bao nhiêu thao tác để có thể nhận được quà từ thầy Lữ.

Sample Input

3
010011
0
1111000

Sample Output

2
-1
0

SubTask

• SubTask 1: ~50\%~ số test với ~1 \leq N \leq 10~ và ~1 \leq T \leq 50~.
• SubTask 2: ~50\%~ số test còn lại, không có ràng buộc gì thêm.