RR và TA ngoài việc làm admin ở VNOI còn có nghề tay trái là người mẫu chụp ảnh trang bìa. Nghề này giúp đôi bạn không những nuôi sống được bản thân mà còn dành dụm được một số tiền kha khá. Vào một ngày đẹp trời, hai người quyết định đi tìm cho mình một tổ ấm. Các bạn đừng suy nghĩ lệch lạc, họ chỉ muốn mua hai ngồi nhà ở gần nhau để tiện bề đàm đạo với nhau về nhân tình thế thái, V-Pop, K-Pop và các thứ tương tự ...

RR và TA tìm mãi mới ra một khu phố rất đặc biệt mà hai người rất hài lòng. Ngoài NN ngồi nhà đẹp rạng ngời được đánh số từ 11 đến NN thì hệ thống đường xá của khu phố này cũng rất đáng chú ý. Tại đây, một số cặp ngôi nhà được nối với nhau bởi một con phố có độ dài một đơn vị. Điều này thì chẳng có gì lạ, nhưng đặc biệt là số lượng các con phố dù rất ít nhưng lại được thiết kế rất khoa học. Cụ thể là chỉ có N−1N−1 con phố nhưng cũng đủ để hai ngôi nhà bất kì đều đến được nhau. Mua nhà ở đây thì không sợ bị lạc mà chỉ đường cho bạn bè đến chơi cũng tiện, hạnh phúc là đây rồi! Thế là RR và TA hăm hở đi rút tiền mua nhà.

flashmt (vừa trúng vé số) cũng định mua nhà ở khu phố này. Nhưng buồn một nỗi, thầy phong thủy trứ danh technolt (cũng là nghề tay trái thôi) lại phán rằng flashmt và "đôi bạn hoàn hảo" RR - TA không hợp tuổi nên anh không nên ở gần hai người này, nếu không sự nghiệp cũng tiêu tan mà tình duyên cũng ngang trái. Nhưng vì là bạn thân của hai người, flashmt vẫn muốn mua nhà ở đây để tiện bề hú hí với nhau. Thầy phong thủy cảnh báo flashmt rằng độ an toàn của flashmt chính bằng khoảng cách từ nhà anh đến ngôi nhà gần nhất trong số hai ngôi nhà của RR và TA. Muốn được bình yên thì dĩ nhiên độ an toàn phải càng lớn càng tốt!

Biết được vị trí hai ngôi nhà của RR và TA, bạn hãy tính xem độ an toàn lớn nhất mà flashmt có thể đạt được là bao nhiêu!

Input

Dòng đầu ghi số nguyên dương TT - số bộ test (T≤5)(T≤5).

Tiếp theo là TT test, mỗi test gồm:

Dòng đầu tiên chứa số nguyên dương NN (1≤N≤50000)(1≤N≤50000) .

Tiếp theo là N−1N−1 dòng, mỗi dòng gồm 22 số nguyên dương u,vu,v cho biết có cạnh nối giữa đỉnh ngôi nhà uu và ngôi nhà vv.

Dòng tiếp theo chứa số nguyên dương QQ (1≤Q≤50000)(1≤Q≤50000).

QQ dòng tiếp theo, mỗi dòng gồm 22số nguyên dương u,vu,v mô tả vị trí hai ngôi nhà của RR và TA.

Các dấu cách và dòng trống thừa có thể xuất hiện ở bất kỳ vị trí nào trong file input.

Output

Output của mỗi bộ test gồm QQ dòng. Mỗi dòng in ra một số nguyên dương duy nhất là đáp án của truy vấn tương ứng.

Giới hạn

Trong 30%30% số test, 1≤N,Q≤1001≤N,Q≤100.

input:

1
7
1 2
1 3
3 4
3 5
3 6
5 7
7
3 7
5 7
4 6
1 2
1 1
3 5
7 2

output:

2
3
3
3
3
2
3

Các học sinh khi đến thực tập trong phòng máy tính thường hay chơi trò chơi điện tử trên mạng. Để ngăn ngừa, người trực phòng máy đã ngắt tất cả các máy tính ra khỏi mạng và xếp chúng thành một dãy trên một cái bàn dài và gắn chặt máy xuống mặt bàn rồi đánh số thứ tự các máy từ 11 đến NN theo chiều từ trái sang phải. Các học sinh tinh nghịch không chịu thua, họ đã quyết định tìm cách nối các máy trên bàn bởi các đoạn dây nối sao cho mỗi máy được nối với ít nhất một máy khác. Để tiến hành công việc này, họ đã đo khoảng cách giữa hai máy liên tiếp. Bạn hãy giúp các học sinh này tìm cách nối mạng thoả mãn yêu cầu đặt ra sao cho tổng độ dài cáp nối phải sử dụng là ít nhất.

Input

Dòng đầu tiên chứa số lượng máy NN (1≤N≤25000)(1≤N≤25000).

Dòng thứ ii trong số N−1N−1 dòng tiếp theo chứa các khoảng cách từ máy ii đến máy i+1i+1 (i=1(i=1, 22, ..., N−1)N−1). Giả thiết rằng khoảng cách từ máy 11 đến máy NN không vượt quá 106106.

Output

Ghi ra độ dài của cáp nối cần sử dụng.

Sample Input

6
2
2
3
2
2

output:

7

Như vậy là chỉ còn một tuần nữa, quả bóng Tango 12 sẽ bắt đầu lăn trên các sân cỏ Poland và Ukraine, 2 quốc gia đăng cai tổ chức EURO 2012 - ngày hội bóng đá được mong chờ nhất trong năm nay. Trong bầu không khí đang nóng dần lên từng ngày này, EURO 2012 đã được rất nhiều doanh nghiệp chọn làm chủ đề cho các chương trình khuyến mãi hay sự kiện với mục đích thu hút sự quan tâm từ lực lượng đông đảo fan hâm mộ môn thể thao vua. Do đó, các nhà tổ chức kì thi Virtual Marathon 2012 (VM12) quyết định treo giải thưởng một cặp vé xem trận chung kết dành cho đội vô địch kì thi này. Đội của Raldono và Balitello, hai nhân vật chính của chúng ta hôm nay, dù đã cố gắng hết sức nhưng đành dừng bước ở vị trí thứ 7, nhận được giải khuyến khích cùng một phần quà từ ban tổ chức.

Phần quà là TT tấm poster hình chữ nhật, mỗi tấm được chia ra thành M×NM×N ô vuông nhỏ (kích thước M,NM,N cho các tấm poster có thể khác nhau). Trong đó, mỗi ô là một tấm thẻ sưu tập hình các cầu thủ nổi tiếng. Raldono quyết định chia các tấm thẻ cho hai người theo cách sau. Ban đầu mỗi người sẽ chọn tất cả tấm thẻ có hình cầu thủ mình yêu thích, sau đó những tấm thẻ còn lại trên poster sẽ được chia ngẫu nhiên. Balitello lại muốn sau khi chia xong các tấm thẻ, nếu cắt ra 1 hình vuông bất kì (có các cạnh song song với cạnh của poster) từ tấm poster thì chênh lệch số thẻ được chia cho mỗi người trong hình vuông đó không vượt quá 22.

Ví dụ trong hình trên, những tấm thẻ Raldono chọn là ô màu vàng, Balitello chọn là ô màu xanh thì 2 cách chia đầu là hợp lệ, 2 cách chia sau là không hợp lệ (những hình vuông được viền đỏ không thỏa yêu cầu).

Với mỗi tấm poster, cho biết những tấm thẻ có hình cầu thủ yêu thích của mỗi người, hãy giúp Raldono và Balitello đếm xem có tất cả bao nhiêu cách chia các tấm thẻ trên tấm poster đó thỏa yêu cầu của cả hai đặt ra.

Input

Dòng 1 ghi số TT, số tấm poster (1≤T≤1000)(1≤T≤1000).

Tiếp theo là TT bộ test, mỗi bộ được mô tả như sau:

Dòng đầu ghi số MM và NN (1≤M,N≤5)(1≤M,N≤5).

Dòng thứ ii trong MM dòng tiếp theo gồm NN kí tự, kí tự thứ jj mô tả tấm thẻ ở hàng ii cột jj của tấm poster ('R' nếu chứa hình cầu thủ Raldono yêu thích, 'B' nếu chứa hình cầu thủ Balitello yêu thích, '.' là những tấm thẻ sẽ được chia ngẫu nhiên).

Output

Xuất ra TT dòng, mỗi dòng chứa kết quả là số cách chia cho tấm poster tương ứng.

Sample Input

input:

5 2 2 BR RB 4 4 ..RR .BRR .BB. .... 2 3 ... BBR 3 3 BBB BR. ... 3 3 ... .R. ...

output:

1 0 6 3 102

Max - Min của đoạn:

algorit là một nhà toán học đại tài, người có chỉ số iq cao nhất nhân loại nếu đếm ngược. Đặc biệt anh rất thích thú với những thứ to và nhỏ, các con số không phải là ngoại lệ. Bởi vậy hôm nay algorit đang thắc mắc một bài toán như sau :

Bạn được cung cấp một dãy số gồm nn số nguyên A1,A2,...,AnA1,A2,...,An.

Nhiệm vụ của bạn là đếm số lượng đoạn con có max−min=kmax−min=k. Ở đây maxmax và minmin là giá trị lớn nhất và giá trị nhỏ nhất của đoạn con đó.

algorit suy nghĩ bài toán này đến mức hói cả đầu mà vẫn chưa nghĩ ra, các bạn hãy giúp algorit nhé !

Input

Dòng đầu tiên gồm 2 số nguyên n,k(0≤k≤109)n,k(0≤k≤109).

Dòng thứ 2 gồm nn số nguyên A1,A2,A3,...,An(−109≤Ai≤109)A1,A2,A3,...,An(−109≤Ai≤109).

Output

Gồm một số nguyên duy nhất là số lượng đoạn con thỏa mãn.

SampleInput:

input: 

5 2
1 2 1 3 3

output:

6

Ràng buộc :

40% số điểm tương ứng với : n≤103n≤103.

30% số điểm tương ứng với : n≤105n≤105.

30% số điểm tương ứng với : n≤5∗105n≤5∗105.