Cho tờ giấy hình chữ nhật có kích thước ~a \times b~ ~(a > b)~. tahp sau đó gấp chéo tờ giấy tạo thành đường gấp có góc ~45~ ~độ~, một mép trùng với một cạnh của tờ giấy, sau đó cắt phần giấy thừa không bị gấp đè lên đi. Sau khi cắt thì tahp sẽ có một mảnh giấy hình vuông kích thước ~b~ x ~b~ và một mảnh kích thước ~b \times (a - b)~. tahp lại tiếp tục thực hiện thao tác như trên với mảnh giấy ~b \times (a - b)~ cho đến khi tất cả mảnh giấy đều là hình vuông.

Yêu cầu: hãy xác định số lần tahp cần cắt để các mảnh giấy trở thành hình vuông.

Input

• Dòng đầu tiên ~t~ số lượng test case ~(1 \le t \le 100)~.
• Gồm ~t~ dòng mỗi dòng chứa hai số nguyên ~a~ và ~b~ ~(1 \le a, b \le 10^{9})~, cách bởi ~1~ dấu cách.

Output

• Ghi ra số lần cắt.

Sample Input

1
10 7

Sample Output

5

Subtask

• ~50\%~ số test có ~t \le 10~ và ~(1 \le a, b \le 10^{6})~
• Số test còn lại không có điều kiện gì thêm.

Note

Ta có ~a~, ~b~ ~(a > b)~ là độ dài các cạnh của hình có diện tích bé nhất sau mỗi lần cắt.

Ta có: ~a = 10~, ~b = 7~

• Lần cắt thứ ~1~ : ~a~ = ~7~, ~b~ = ~3~.
• Lần cắt thứ ~2~ : ~a~ = ~4~, ~b~ = ~3~.
• Lần cắt thứ ~3~ : ~a~ = ~3~, ~b~ = ~1~.
• Lần cắt thứ ~4~ : ~a~ = ~2~, ~b~ = ~1~.
• Lần cắt thứ ~5~ : ~a~ = ~1~, ~b~ = ~1~.

Vậy sau ~5~ lần cắt các mảnh giấy đều thành hình vuông.

Bedao tổ chức một giải đấu bóng đá với sự tham gia của nhiều đội trên cả nước. Trong danh sách có ~n~ đội bóng, mỗi đội gặp nhau đúng ~2~ lần trong một mùa giải và có tất cả ~n \times (n-1)~ trận đấu, khi chưa có trận đấu nào diễn ra (vòng ~0~) thì đội thứ ~i~ sẽ xếp thứ hạng ~a_i~ trên bảng xếp hạng (biết rằng bảng xếp hạng ban đầu này được xếp theo thứ tự từ điển qua tên các đội bóng), ta có thể xem đây là tên của đội bóng thứ ~i~.

Cách phân hạng của giải đấu như sau:

• Một trong hai đội thắng sẽ đạt được ~3~ điểm.
• Hai đội hòa nhau thì mỗi đội sẽ đạt được ~1~ điểm.
• Một trong hai đội thua sẽ không có điểm.

Với ~Pts~ là số điểm đạt được của đội bóng, ~GD~ là hiệu số bàn thắng ghi được và số bàn bị thủng lưới của đội bóng. Biết rằng, đội ~a_i~ xếp hạng cao hơn đội ~a_j~ khi:

• ~Pts~ đội ~a_i~ phải lớn hơn đội ~a_j~.
• Nếu ~Pts~ hai đội bằng nhau thì ~GD~ đội ~a_i~ phải lớn hơn đội ~a_j~.
• Nếu ~GD~ hai đội bằng nhau thì đội ~a_i~ phải có số bàn thắng nhiều hơn đội ~a_j~.
• Nếu số bàn thắng hai đội vẫn bằng nhau thì hai đội sẽ xếp chung một hạng trên bảng xếp hạng.

Để tổ chức một giải đấu tầm cỡ quốc gia như thế, Bedao phải thiết kế một bảng xếp hạng sao cho mọi người có thể dễ dàng theo dõi nhất, nhưng kinh phí thì có hạn cho nên bảng xếp hạng của giải chỉ gồm thông tin của đội vô địch, với cách làm này Bedao cũng sẽ đỡ phải thưởng tiền cho những đội xếp sau.

Yêu cầu: in ra danh sách đội vô địch (xếp thứ ~1~) sau ~n \times (n-1)~ trận đấu.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(2 \leq n \leq 20)~ là số đội tham dự giải đấu.
• Dòng thứ hai chứa các số ~a_1, a_2, \dots, a_n~ ~(1 \leq a_i \leq n)~ là thứ hạng của các đội ở vòng ~0~, khi ở vòng này thì thứ hạng đội được xếp theo thứ tự từ điển theo tên đội và các phần tử ~a_1, a_2, \dots, a_n~ đôi một phân biệt nhau.
• ~n \times (n-1)~ dòng tiếp theo là thông tin các trận đấu diễn ra ở giải đấu, thông tin có dạng là: ~a_i~ ~a_j~ ~x~ ~y~ ~(0 \leq x,y \leq 30)~. Biết rằng ~a_i~ là thứ hạng ở vòng ~0~ của đội bóng thứ ~i~, ~a_j~ là thứ hạng ở vòng ~0~ của đội bóng thứ ~j~, ~x~ là số bàn ghi được của đội bóng thứ ~i~, ~y~ là số bàn ghi được của đội bóng thứ ~j~.

Output

• Gồm một dòng là danh sách đội vô địch sau giải đấu, danh sách có thể in theo thứ tự bất kỳ và các số nguyên trong danh sách là thứ hạng của đội ở vòng ~0~.

Sample Input 1

4
2 1 3 4 
4 2 16 8
1 4 8 16
2 3 29 29
4 3 16 8
1 3 29 29
2 1 29 29
4 3 16 8
4 2 16 8
2 3 29 29
1 4 8 16
1 3 29 29
2 1 29 29

Sample Output 1

4 

Sample Input 2

3
3 1 2
1 2 0 0
3 2 1 2
1 3 0 3
2 1 2 1
3 2 2 0
3 1 2 2

Sample Output 2

3

Sample Input 3

3
3 1 2
1 2 0 0
3 2 1 2
1 3 0 3
2 1 6 1
3 2 2 0
3 1 2 2

Sample Output 3

2 3 

Ở trong thành phố Bedao, nơi mọi người rất yêu thích những cái cây. Hôm nay thị trưởng Copium đã cho tổ chức một cuộc thi tô màu, đề bài là cho một cây với ~n~ node và ~n - 1~ cạnh, cạnh thứ ~i~ nối giữa ~2~ node ~u_i~ và ~v_i~ có chiều dài là ~w_i~. Hãy tô mỗi node màu đỏ hoặc đen sao cho độ dài giữa ~2~ node cùng màu bất kỳ luôn là chẵn. Phần thưởng dành cho người nhanh nhất sẽ là một khoản tiền rất lớn, nên bạn hãy cố gắng chiến thắng cuộc thi đó nhé!

Input

• Dòng đầu tiên chứa số nguyên ~n~, là số node của cây ~(1 \le n \le 10^5)~
• Trong ~n - 1~ dòng kế tiếp, mỗi dòng chứa ~3~ số nguyên ~u_i~, ~v_i~ và ~w_i~, biểu diễn cạnh nối giữa ~u_i~, ~v_i~ và có độ dài là ~w_i~ ~(1 \le u_i, v_i \le n, 1 \le w_i \le 10^9)~

Output

• Gồm ~n~ số nguyên. Số thứ ~i~ là ~0~ nếu node ~i~ được tô màu đỏ, còn ~1~ nếu node ~i~ được tô màu đen. Nếu có nhiều phương án, hãy in ra phương án bất kỳ.

Sample Input 1

3
2 3 1
2 1 2

Sample Output 1

1 1 0

Sample Input 2

5
2 5 2
2 3 10
1 3 8
3 4 2

Sample Output 2

1 0 1 0 1

Subtask

• ~20\%~ số test có ~n \le 10~.
• ~80\%~ số test còn lại không có điều kiện gì thêm.

Note

Trong ví dụ thứ ~2~ sẽ có nhiều đáp án khác nhau, chẳng hạn như ~[1, 1, 1, 1, 1]~ vẫn được xem là hợp lệ.

~Copium~ rất mê cái đẹp, anh ta không những mê gái mà còn mê cả xâu. Một xâu ~Copium~ cho là đẹp nếu nó tồn tại một cách sắp xếp sao cho xâu đó là một palindrome. Một hôm một người bạn của anh ta đưa cho anh một xâu ~S~, và với tính tò mò của mình, ~Copium~ đã dành hàng tiếng để đếm số xâu con ~[l, r]~ ~(1 \le l \le r \le n)~ của xâu ~S~ sao cho nó là một xâu đẹp. Nhưng vì xâu ~S~ quá dài nên ~Copium~ đang cần bạn giúp!

Một xâu palindrome được định nghĩa là xâu khi đọc từ trái sang phải và ngược lại đều có kết quả như nhau.

Input

• Dòng đầu gồm một số nguyên ~n~ là chiều dài của xâu ~S~ ~(1 \le n \le 10^5)~
• Dòng thứ hai là xâu ~S~ có chiều dài ~n~ chỉ gồm các ký tự từ ~[a, z]~ viết thường và các số thuộc ~[0, 9]~

Output

• In ra một số duy nhất là số xâu con đẹp trong xâu ~S~.

Sample Input 1

5
abacc

Sample Output 1

9

Sample Input 2

5
bedao

Sample Output 2

5

Subtask

• ~10\%~ số test thoả mãn xâu ~S~ chỉ gồm ~2~ ký tự 'a' và 'b'
• ~30\%~ số test tiếp theo có ~n \le 2 \times 10^3~
• ~60\%~ số test còn lại không có điều kiện gì thêm

Trong bài có thể xuất hiện nhiều khái niệm mới, đầu tiên bạn cần biết về nhân ma trận.

Cho ~A~ là ~1~ ma trận vuông có kích thước ~n \times n~ và ~A~ chỉ gồm các ô có giá trị ~0~ hoặc ~1~. Tìm số nguyên dương ~k~ nhỏ nhất sao cho lũy thừa bậc ~k~ của ma trận ~A~ là ma trận gồm toàn các số ~0~, biết rằng lũy thừa của một ma trận được mô tả như sau:

Input:

• Dòng đầu gồm ~2~ số nguyên ~n~ ~(1 \leq n \leq 5 \times 10^5)~ và ~m~ ~(0 \leq m \leq 5 \times 10^5)~ trong đó ~n~ là kích thước ma trận còn ~m~ là số ô có giá trị bằng ~1~ trên ma trận ~A~.
• ~m~ dòng tiếp theo, trên mỗi dòng có một cặp số ~(i, j)~ ~(1 \leq i, j \leq n)~ là tọa độ của các ô có giá trị bằng ~1~ trên ma trận ~A~, dữ liệu đảm bảo rằng không có cặp số ~(i, j)~ nào xuất hiện ~2~ lần. Một ô có tọa độ ~(i, j)~ nếu như nó nằm tại dòng thứ ~i~ tính từ trên xuống và cột thứ ~j~ tính từ bên trái sang của ma trận ~A~, nếu toạ độ của ô không nằm trong ~m~ cặp số được cho thì ô đó mặc định có giá trị bằng ~0~.

Output:

• In ra số nguyên dương ~k~ nhỏ nhất hoặc ~-1~ nếu ~k~ không tồn tại.

Sample Input 1:

4 2
1 2
4 3

Sample Output 1:

2

Sample Input 2:

3 3
1 1
2 2
3 3

Sample Output 2:

-1

Subtask

• ~10\%~ số test có ~1 \le n \le 4~.
• ~30\%~ số test khác có ~1 \le n \le 60~.
• ~60\%~ số test còn lại không có điều kiện gì thêm.

Note

• Ở Sample test 1, dễ thấy ~A^2~ là ma trận toàn ~0~.

• Ở Sample test 2, ma trận ~A~ đã cho được gọi là một Identity matrix, khi lấy lũy thừa bậc ~k~ của một Identity matrix thì giá trị các ô trên ma trận hoàn toàn giữ nguyên.