Trong một thị trấn nhỏ, có một cậu bé tên là Sơn đam mê khám phá về lập trình. Một ngày, cậu nhận được một cuốn sách kỳ lạ có tên Những Dãy Ngoặc Huyền Bí. Trong cuốn sách này, có một bí mật: cách kết hợp các dãy ngoặc để tạo ra những điều kỳ diệu. Sơn học được rằng một dãy ngoặc được gọi là kì bí khi nó tuân thủ các quy tắc sau:

• Dãy ngoặc rỗng là một dãy ngoặc kì bí.
• Nếu ~A~ là dãy ngoặc kì bí thì ~(A)~ là một dãy ngoặc kì bí.
• Nếu ~A~ và ~B~ là 2 dãy ngoặc kì bí thì ~AB~ là 1 dãy ngoặc kì bí.

Từ đó, Sơn đã áp dụng những kiến thức này vào cuộc sống hàng ngày của mình, giúp anh trở thành một lập trình viên đẳng cấp. Sơn muốn đố bạn rằng: Cho một dãy ngoặc bất kì, kiểm tra xem đó có phải dãy ngoặc kì bí hay không?

Input

• Dòng đầu tiên là số lượng bộ test T (T ≤ 20).
• Mỗi test gồm 1 dãy ngoặc S có độ dài không vượt quá 10000.
• Dãy ngoặc S chỉ chứa các kí tự: ~[~, ~]~, ~(~, ~)~, ~\{~, ~\}~, "" (rỗng)

Output

• Với mỗi test, in ra Yes nếu S là dãy ngoặc đúng, in ra No trong trường hợp ngược lại.

Chia độ khó

Sample Input:

2  
[()]{}{[]()}
[(])

Sample Output:

Yes
No

Ta gọi một số có dạng ~p^q~ là lũy thừa cao của một số nguyên tố khi và chỉ khi ~p~ là một số nguyên tố và ~q > 1~

Cho một số ~N~ bất kì, cho biết đó có phải lũy thừa cao của một số nguyên tố hay không? Nếu có thì in ra 2 số ~p~, ~q~, nếu không thì in ra ~0~

Input

• 1 dòng duy nhất chứa ~N (N <= 10^{18})~

Output

• 1 dòng duy nhất là kết quả ~p~, ~q~ nếu có hoặc ~0~ nếu không

Sample Input 1

27

Sample output 1

3 3

Sample Input 2

10

Sample output 2

0

Để tăng số lượng thí sinh tham dự cho bảng thi đôi nam nữ kì thi AlgoSec Battle mùa 3 tới, CLB TAS quyết định tổ chức ghép đôi theo quy tắc như sau:

1. Các thí sinh nam sẽ điền form đăng ký ghép đôi và trình bày các điểm mạnh cũng như mong muốn của bản thân
2. Sau khi bước 1 hoàn tất, các thí sinh nữ sẽ chọn từ form số thứ tự của 2 bạn nam mà mình muốn được ghép đôi cùng

Vì không để ý nên tới hạn chót H mới đăng ký ghép đôi cho mình. Lúc này trong danh sách đã có ~N~ bạn nữ và ~N + 1~ bạn nam đăng ký. Vì sợ đăng ký trùng với các thí sinh đăng ký trước sẽ không thể ghép đôi được, H quyết định lập trình một thuật toán để đếm xem có bao nhiêu cách khác nhau để BTC có thể ghép đôi cho tất cả mọi người ( sẽ đưa ra lựa chọn của mình sau khi phân tích).

Vì viết mãi mà thuật toán chạy không đúng nên H quyết định nhờ sự giúp đỡ của bạn. Hãy giúp bạn ấy có thể ghép đôi suôn sẻ cho kì thi sắp tới nhé!

Input

• Dòng đầu chứa số nguyên ~N~ là số lượng bạn nữ đã đăng ký.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa cặp số nguyên ~A_i~, ~B_i~ là chỉ số của 2 bạn nam mà bạn nữ thứ ~i~ mong muốn ghép đôi. ~1 ≤ A_i < B_i ≤ N + 1~.

Output

• Chứa một số duy nhất là đáp số bài toán.

Chia độ khó

Sample Input 1

2
2 3
2 3

Sample Output 1

2

Sample Input 2

3
1 2
1 2
1 2

Sample Output 2

0

Giải thích

Ví dụ 1: Do 2 bạn nữ 1 và 2 đều chọn 2 bạn nam 2 và 3 nên 2 bạn này sẽ được ghép cho 2 người. Hảo chỉ có thể chọn bạn Nam số 1, vì vậy 2 cách chọn hợp lý cho Hảo là (1,2) và (1,3).

Ví dụ 2: Do có 3 bạn nữ đều muốn chọn bạn nam 1 và 2 nên dù Hảo chọn như thế nào cũng không thể sắp xếp được.

Công ty VTCorp có ~N~ nhân viên được đánh số từ ~1~ tới ~N~. Trừ CEO (nhân viên số 1) ra thì nhân viên thứ ~P_i~ sẽ là cấp trên trực tiếp của nhân viên thứ ~i~.

Quan hệ cấp bậc trong công ty tạo thành một cấu trúc hình cây. Quan hệ này có tính bắc cầu: nếu nhân viên ~x~ là cấp trên của nhân viên ~y~ và nhân viên ~y~ là cấp trên của nhân viên ~z~ thì nhân viên ~x~ là cấp trên của nhân viên ~z~.

Biết rằng nhân viên thứ ~i~ có thu nhập là ~S_i~. Hãy đếm số cách chọn 3 nhân viên ~(x, y, z)~ khác nhau sao cho:

• Nhân viên thứ ~x~ là cấp trên của nhân viên ~y~ và ~z~.
• Thu nhập của nhân viên thứ ~x~ cao hơn thu nhập của nhân viên thứ ~y~ và thứ ~z~.
• Bộ ba ~(x, y, z)~ và ~(x, z, y)~ được coi là giống nhau.

Input

• Dòng 1: Chứa số nguyên ~N~ thể hiện số nhân viên.
• Dòng 2: Chứa một số nguyên dương ~S_1~ thể hiện tiền lương của CEO (nhân viên ~1~).
• ~N-1~ dòng tiếp theo: Dòng thứ ~i~ chứa ~2~ số nguyên dương ~P_{i+1}~ và ~S_{i+1}~ lần lượt thể hiện cấp trên trực tiếp và tiền lương của nhân viên thứ ~i + 1~

Output

• Một số nguyên duy nhất là số lượng bộ ba thỏa mãn.
• Kết quả có thể vượt quá giới hạn số nguyên ~32~ bit.

Chia độ khó

Sample input

5
3
1 2
1 2
3 2
3 1

Sample output

6

Giải thích

Sơ đồ biểu diễn cấp bậc của các nhân viên sẽ như sau:

  1
 / \
2   3
   / \
  4   5

Ta có 6 bộ ba như sau:

1. ~(1, 2, 3)~ - CEO có lương bằng ~3~ lớn hơn nhân viên thứ ~2~ và thứ ~3~ với tiền lương của mỗi người là ~2~. CEO là cấp trên của cả nhân viên ~2~ và ~3~.
2. ~(1, 2, 4)~ - Tiền lương của nhân viên thứ ~2~ và thứ ~4~ đều là ~2~ và nhỏ hơn tiền lương của CEO và cả ~2~ đều là cấp dưới.
3. ~(1, 2, 5)~
4. ~(1, 3, 4)~
5. ~(1, 3, 5)~
6. ~(1, 4, 5)~

Bộ ~(3, 4, 5)~ không được tính vì lương của nhân viên thứ ~3~ chỉ bằng chứ không cao hơn tiền lương của nhân viên thứ ~4~.