Cho hai xâu ký tự ~a~ và ~b~. Biết rằng xâu ~a~ chỉ chứa các chữ số 0 và 1, còn xâu ~b~ chỉ chứa các chữ cái in thường. Bạn cần tìm hai xâu ký tự ~p~ và ~q~ sao cho:

• ~p~ và ~q~ là hai xâu khác rỗng;

• ~p~ và ~q~ chỉ chứa các chữ cái in thường;

• ~p \ne q~.

Nếu thay mọi chữ số 0 trong ~a~ bởi ~p~ và thay mọi chữ số 1 trong ~a~ bởi ~q~ thì ta được xâu ~b~.

Yêu cầu: Hãy đếm số cách chọn ra hai xâu ~p~ và ~q~ thỏa mãn các điều kiện trên.

Input

• Dòng đầu tiên chứa số nguyên ~T~ là số bộ dữ liệu. Tiếp theo là các bộ dữ liệu, mỗi bộ dữ liệu được mô tả theo khuôn dạng sau:

  • Dòng thứ nhất chứa xâu ~a~. Xâu này chỉ chứa các chữ số 0 và 1; và chắc chắn có ít nhất một chữ số 0 và ít nhất một chữ số 1.

  • Dòng thứ hai chứa xâu ~b~. Xâu này chỉ chứa các chữ cái in thường.

Gọi:

• ~|a|~ là độ dài xâu ~a~;

• ~|b|~ là độ dài xâu ~b~;

• ~\Sigma_a~ là độ dài xâu ~a~ trong tất cả các bộ dữ liệu;

• ~\Sigma_b~ là độ dài xâu ~b~ trong tất cả các bộ dữ liệu.

Dữ liệu đảm bảo:

• ~2 \le |a| \le 10^5~ và ~1 \le |b| \le 10^6~;

• ~\Sigma_a \le 5 \cdot 10^5~ và ~\Sigma_b \le 5 \cdot 10^6~.

Output

Với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên là số cách chọn hai xâu ~p~ và ~q~ thỏa mãn các điều kiện trên.

Scoring

Sample Input 1

2
01
zzzzzz
001
cucucucute

Sample Output 1

4
2

Notes

Trong bộ dữ liệu thứ nhất, các cặp xâu ~(p,q)~ có thể chọn là:

• z và zzzzz;

• zz và zzzz;

• zzzz và zz;

• zzzzz và z.

Trong bộ dữ liệu thứ hai, các cặp xâu ~(p,q)~ có thể chọn là:

• cu và cucute;

• cucu và te.