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

Để chuẩn bị cho cuộc thi AlgoSec Battle 2, CLB TAS muốn chọn 3 địa điểm tại trường ĐH Thủy Lợi để đặt standee quảng bá cho sự kiện. Theo niềm tin của anh Việt Thảo thì bộ 3 địa điểm "vàng" phải có tọa độ tạo thành một tam giác cân (nhưng không đều).

Sau khi nhận được danh sách các địa điểm có thể đặt standee từ các thành viên TAS, anh muốn đếm xem có bao nhiêu cách chọn một bộ 3 địa điểm "vàng" cho sự kiện sắp tới.

Input

• Dòng đầu ghi số nguyên dương ~N~ là số địa điểm.
• N dòng sau, mỗi dòng ghi cặp số nguyên dương ~X_i~, ~Y_i~ là tọa độ của một địa điểm (~1 <= X_i <= Y_i <= 10^6~). Không có 3 địa điểm nào thẳng hàng.

Output

• In ra một số nguyên duy nhất là số bộ 3 địa điểm "vàng" có thể chọn.

Chia độ khó

Sample input

5
1 2
2 1
2 2
1 1
1000 1000000

Sample Output

4

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

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~.