Hân là một học sinh rất thích các cấu trúc dữ liệu. Giải quyết các bài toán truy vấn là thú vui lớn nhất của cậu, chỉ xếp sau anime. Một hôm, sau khi làm đủ 100 bài toán truy vấn trong một ngày, Hân cảm thấy các bài tập chưa đủ khó và quyết định tự nghĩ ra một bài toán khác để thách thức bản thân. Bài toán của Hân như sau:

Ban đầu Hân có một số nguyên \(x\), giá trị ban đầu bằng \(1\). Cậu có \(Q\) truy vấn như sau:

• \(1\ val:\) \(x = x * val\).
• \(2\ pos:\) \(x = x / val\), với \(val\) là giá trị xuất hiện ở truy vấn thứ \(pos\). Đảm bảo rằng truy vấn thứ \(pos\) là truy vấn loại 1 và mỗi thao tác loại 1 bị chia tối đa một lần.

Với mỗi truy vấn, in ra kết quả của số \(x\) khi chia lấy dư cho \(M\).

Vì đã code quá 180 phút nên Hân không còn đủ cảm hứng để giải quyết bài toán này. Bạn hãy giúp Hân nhé.

Input:

• Dòng đầu tiên chứa số nguyên \(t\), là số lượng testcases \((1 \leq t \leq 5)\)
• Với mỗi testcase, dòng đầu tiên chứa 2 số nguyên \(Q, M \ (1 \leq Q \leq 10^5 ,\ 1 \leq M \leq 10^9)\)
• \(Q\) dòng tiếp theo, dòng \(i\) thể hiện truy vấn thứ \(i\).
  Truy vấn loại 1 có dạng \(1\ val\ (1 \leq val \leq M)\).
  Truy vấn loại 2 có dạng \(2\ pos\ (1 \leq pos \leq Q)\)

Output:

Với mỗi truy vấn, in ra giá trị của \(x\) khi chia lấy dư cho \(M\).

Ví dụ:

**Input: **

1
10 1000
1 2
2 1
1 2
1 10
2 3
2 4
1 6
1 7
1 12
2 7

**Output: **

2
1
2
20
10
1
6
42
504
84

Ràng buộc:

• Subtask 1: \(\ 1 \leq Q \leq 500\)
• Subtask 2: \(\ 1 \leq Q \leq 10^5\)