Có ba con rùa nằm trên một đường thẳng được mô tả như là trục số ~Ox~. Ban đầu, con thứ nhất ở vị trí ~x = a~, con thứ hai ở vị trí ~x = b~ và con thứ ba ở vị trí ~x = c~. Đôi khi, một số con rùa có thể ở cùng một vị trí.

Trong một bước di chuyển, mỗi con rùa có thể di chuyển đến vị trí ~x - 1~ (đi sang trái) hoặc là đến vị trí ~x + 1~ (đi sang phải) hoặc giữ nguyên vị trí.

Biết rằng ba con rùa đều muốn đến gần nhau hơn với không quá một bước di chuyển. Hãy tính tổng khoảng cách nhỏ nhất có thể giữa mỗi cặp rùa với giả định cả ba con rùa đều di chuyển tối ưu.

Bạn phải trả lời ~q~ truy vấn độc lập.

Dữ liệu:

• Dòng đầu tiên của đầu vào chứa số nguyên ~q (1 \le q \le 10^4)~ là số truy vấn.
• Tiếp theo là ~q~ truy vấn, mỗi truy vấn một dòng chứa lần lượt ba số nguyên ~a, b, c~ viết cách nhau một dấu cách.

Kết quả:

• Ghi ra ~q~ dòng, dòng thứ ~i~ ghi một số nguyên duy nhất là đáp án tương ứng với của truy vấn thứ ~i~ từ dữ liệu vào.

Ràng buộc:

• Có ~70\%~ số test ứng với ~70\%~ số điểm của bài với ~-10^6 \le a, b, c \le 10^6~.
• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài với ~-10^{12} \le a, b, c \le 10^{12}~.

  Ví dụ:

Sample Input

2
3 3 4
10 20 30

Sample Output

0
36

Giải thích

Trong ví dụ có ~2~ truy vấn:

• Truy vấn ~1~: ~a = b = 3, c= 4~. Con rùa thứ nhất và thứ hai đang ở cùng vị trí với nhau nên không cần di chuyển nữa, con thứ ba ở vị trí ~4~, nó sang trái trong ~1~ di chuyển để đến vị trí ~3~. Sau đó cả ba con đều ở cùng vị trí và tổng khoảng cách giữa chúng bằng ~0~.
• Truy vấn ~2~: ~a = 10, b = 20, c = 30~. Con thứ nhất đang ở vị trí ~10~, nó cố gắng đến gần con thứ hai bằng ~1~ bước đi đến vị trí ~11~. Con thứ ba đang ở vị trí ~30~ nó cố gắng đến gần con thứ hai bằng ~1~ bước đi đến vị trí ~29~. Con thứ hai đứng yên. Tổng khoảng cách giữa ba con rùa là ~(20-11) + (29-20) + (29-11)= 36~.

Cho ~n~ chuỗi ký tự ~S_1, S_2, ..., S_n~ khác rỗng, có độ dài có thể khác nhau và chỉ chứa các chữ cái tiếng Anh in thường.

Bạn có thể thực hiện phép di chuyển sau đây: Lấy một ký tự ~c~ bất kỳ trong chuỗi ~S_i~ và chèn ký tự ~c~ này vào một vị trí bất kỳ trong chuỗi ~S_j~. Sau khi lấy ký tự ~c~ trong chuỗi ~S_i~ , ký tự ~c~ sẽ bị xóa khỏi chuỗi ~S_i (1 \le i, j \le n, i \ne j)~.

Bạn được phép thực hiện di chuyển trên với số lần tùy ý (có thể ~0~ lần).

Hỏi sau khi thực hiện các di chuyển như vậy, bạn có thể làm ~n~ chuỗi ký tự đã cho trở nên hoàn toàn bằng nhau hay không.

Ví dụ:

• Với ~n = 2, s_1 =~ "abcade", ~s_2 =~ "cbed" thì câu trả lời là YES.
• Với ~n = 2, s_1 =~ "abcad", ~s_2 = ~"cbed" thì câu trả lời là NO.

Bạn phải trả lời q truy vấn độc lập.

Dữ liệu:

Dòng đầu tiên của đầu vào chứa số nguyên ~q (1 \le q \le 50)~ là số truy vấn. Tiếp theo là ~q~ truy vấn, mỗi truy vấn gồm:

• Dòng thứ nhất chứa số nguyên dương ~n (1 \le n \le 10)~ là số chuỗi ký tự.
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa chuỗi ký tự si, chỉ gồm các chữ cái tiếng Anh in thường. Mỗi chuỗi có không quá ~10^4~ ký tự.

Kết quả:

• Ghi ra q dòng, trong đó dòng thứ i ghi ra từ YES hoặc NO là câu trả lời cho truy vấn thứ ~i~.

Ràng buộc:

• Có ~70\%~ số test ứng với ~70\%~ số điểm của bài có ~1 \le n \le 2~ và các chuỗi ~s_i (1 \le i \le n)~ có độ dài không quá ~50~.
• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài có ~1 \le n \le 10~ và các chuỗi ~s_i (1 \le i \le n)~ có độ dài không quá ~10^5~.

Ví dụ:

Sample Input

3
2
aabb 
cc
2
ab
ab
2
ab
a

Sample Output

YES
YES
NO

Giải thích

Trong test ví dụ Có 3 truy vấn:

• Truy vấn ~1~: ~n = 2, s1 =~ "aabb", ~s2 = ~"cc". Bạn có thể lấy ~1~ ký tự 'a', một ký tự 'b' từ chuỗi ~s_1~ chèn vào ~s_2~, sau đó lấy một ký tự 'c' từ ~s_2~ và chèn vào ~s_1~. Câu trả lời là YES.
• Truy vấn ~2~: ~n = 2, s1 = s2 =~ "ab" đã hoàn toàn bằng nhau, vì vậy bạn không cần thực hiện di chuyển nào. Câu trả lời là YES.
• Truy vấn ~3~: ~n = 2, s1 =~"ab" ~s2 = ~"b", bạn không thể thực hiện di chuyển nào để hai chuỗi này trở nên bằng nhau, câu trả lời là NO.

Cho một dãy gồm ~n~ số nguyên ~a[1], a[2], ..., a[n]~. Trong một thao tác, bạn có thể chọn hai phần tử của dãy và thay thế chúng bằng phần tử tổng của chúng (bạn có thể chèn phần tử tổng này vào vị trí bất kỳ trong dãy).

Ví dụ: Từ mảng ~a = (5,1,4)~, bạn có thể tạo ra các dãy sau: ~(6, 4), (1, 9)~ và ~(5, 5)~ bằng thao tác nói trên.

Nhiệm vụ của bạn là tìm số phần tử tối đa có thể chia hết cho ~5~ trong mảng kết quả sau khi thực hiện một số lần tùy ý thao tác nói trên (có thể là ~0~ lần).

Bạn phải trả lời q truy vấn độc lập.

Dữ liệu:

Dòng đầu tiên của đầu vào chứa một số nguyên ~q (1 \le q \le 100)~ là số truy vấn. Tiếp theo là mô tả ~q~ truy vấn, mỗi truy vấn gồm ~2~ dòng:

• Dòng ~1~: Chứa một số nguyên ~n (1 \le n \le 10^5)~.
• Dòng ~2~: Chứa ~n~ số nguyên ~a[1], a[2], ..., a[n] (1 \le a[i] \le 10^9, 1 \le i \le n)~.

Kết quả:

• Ghi ra ~q~ dòng, dòng thứ ~i~ ghi kết quả của truy vấn thứ ~i~, là một số nguyên cho biết số phần tử tối đa chia hết cho ~5~ trong mảng kết quả sau khi thực hiện một số lần tùy ý thao tác được mô tả trong đề bài.

Ràng buộc:

• Có ~60\%~ số test ứng với ~60\%~ số điểm của bài với ~1 \le n \le 10^2, 1 \le a[i] \le 10~.
• Có ~40\%~ số test ứng với ~40\%~ số điểm của bài với ~1 \le n \le 10^5, 1 \le a[i] \le 10^9~.

  Ví dụ:

Sample Input

2
5 
2 4 5 3 1
4
5 4 1 3

Sample Output

3
2

Giải thích:

Trong test ví dụ có 2 truy vấn:

• Truy vấn ~1~: ~n = 5~, mảng ban đầu là ~(2, 4, 5, 3, 1)~, thu gọn mảng để tăng số phần tử chia hết cho ~5~ bằng ~2~ thao tác cộng: ~2+3, 4+1~, ta được mảng ~3~ phần tử ~(5, 5, 5)~, mảng kết quả có ~3~ phần tử chia hết cho ~5~. Đáp án là ~3~.
• Truy vấn ~2~: ~n = 4~, mảng ban đầu là ~(5, 4, 1, 3)~, thu gọn mảng bằng ~1~ thao tác cộng: ~4+1~ ta được mảng ~3~ phần tử ~(5, 5, 3)~, mảng kết quả có 2 phần tử chia hết cho ~5~. Đáp án là ~2~.

Minh được thầy giáo giao cho một bài tập về nhà là tìm ước số chung lớn nhất của hai số nguyên dương ~A~ và ~B~. Tuy nhiên, do các số này là khá lớn, thầy giáo cho cậu biết ~N~ số nguyên nhỏ mà có tích là ~A~ và ~M~ số nguyên nhỏ mà có tích là ~B~. Nói cách khác, Minh được biết hai dãy ~a[1], a[2], ..., a[N], b[1], b[2], ..., b[M]~ thỏa mãn điều kiện:

• A = a[1] × a[2] × ... × a[N];
• B = b[1] × b[2] × ... × b[M].

Minh cần phải tìm ước số chung lớn nhất của ~A~ và ~B~.

Yêu cầu: Hãy viết chương trình giúp Minh tìm ước số chung lớn nhất của ~A~ và ~B~. Kết quả có thể rất lớn và bạn chỉ cần in ra số dư của phép chia kết quả cho ~(10^9 + 7)~.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên dương ~N (1 \le N \le 10^3)~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~a[1], a[2], ..., a[N] (1 \le a[i] \le 10^5, 1 \le i \le N)~ có tích bằng ~A~;
• Dòng thứ ba chứa số nguyên dương ~M (1 \le M \le 10^3)~;
• Dòng thứ tư chứa ~M~ số nguyên dương ~b[1], b[2], ..., b[M] (1 \le b[i] \le 10^5, 1 \le i \le M)~ có tích bằng ~B~.

Kết quả:

• Ghi ra một dòng ghi một số ~X~ duy nhất là ước chung lớn nhất ~A~ và ~B~. Vì ~X~ có thể rất lớn, bạn chỉ cần in ra số dư của phép chia ~X~ cho ~(10^9 + 7)~.

Ràng buộc:

• Có ~50\%~ số điểm của bài có: ~1 \le M, N \le 10, 1 \le a[i], b[j] \le 50 (1 \le i \le N, 1 \le j \le M)~;
• Có ~50\%~ số điểm của bài có: ~1 \le M, N \le 10^3, 1 \le a[i], b[j] \le 10^5 (1 \le i \le N, 1 \le j \le M)~.

Ví dụ:

Sample Input 1

3
2 3 5
2
4 5

Sample Output 1

10

Sample Input 2

4
6 2 3 4
1
1

Sample Output 2

1

Giải thích:

• Ví dụ ~1~: ~A = 2 × 3 × 5 = 30, B = 4 × 5 = 20~ và ~GCD(A, B) = 10~.
• Ví dụ ~2~: ~A = 2 × 3 × 4 × 6 = 144, B = 1~ và ~GCD(A, B) = 1~.