Hôm nay, Pink Green Peacock (PGP) được học về dãy cấp số cộng và những tính chất lý thú của nó. Nhắc lại một chút, một cấp số cộng (tiếng Anh: arithmetic progression hoặc arithmetic sequence) là một dãy số thoả mãn điều kiện: hai phần tử liên tiếp nhau sai khác nhau một hằng số. Chẳng hạn, dãy số ~3~, ~5~, ~7~, ~9~, ~11~,... là một cấp số cộng với các phân tử liên tiếp sai khác nhau hằng số ~2~. Hằng số sai khác chung được gọi là công sai của cấp số cộng. Các phần tử của nó cũng được gọi là các số hạng.

Là một học sinh giỏi vô địch cấp vũ trụ ngân hà, PGP tất nhiên cảm thấy những kiến thức này rất dễ, và không đủ đô với cậu. Vì vậy cậu nhụt chí học hành, ăn không ngon, ngủ không yên, cân nặng tụt dốc không phanh. Nhận thấy điều đó, thầy dạy toán đã đố PGP một bài toán khó: Tìm công thức tính tổng của ~n~ số hạng đầu tiên của dãy số được cho bởi công thức ~u_i = i^k~, với ~k = 6~. Chỉ chờ có thể, PGP đã thể hiện kỹ năng Toán siêu việt của mình, ngay lập tức giải được bài toán trong sự ngỡ ngàng của thầy giáo.

Tưởng dễ ăn, PGP đã yêu cầu thầy cho bài khó hơn, như thế mới đáng bậc nam nhi. Vì vậy, thầy giáo tăng giới hạn lên ~k = 50~ và PGP nhận lời thách đấu, vì vậy thầy đã cho đấy làm bài tập về nhà để cả lớp suy nghĩ thêm. Đáng buồn thay, PGP tuy rất giỏi, nhưng kỹ năng cũng chỉ có thế, không thể nào hơn được, vì vậy cậu đành chịu thua. Bây giờ hạn chót đang đến rất gần, mà PGP vẫn bất lực như nhân vật chính trong các bộ NTR, vì vậy cậu ấy đành phải cầu cứu các bạn lập trình viên. Hãy giúp PGP chạy deadline bằng cách giải bài toán hóc búa này nhé.

Input:

Dòng đầu tiên chứa một số nguyên dương ~T~ (~T \leq 100~) là số truy vấn.

~T~ dòng tiếp theo, dong thứ ~i~ (~1 \leq i \leq T~) chứa hai số nguyên dương ~n_i~ (~n_i \leq 10^{15}~) và ~k_i~(~k_i \leq 50~).

Output:

Gồm ~T~ dòng. Với dòng thứ ~i~ (~1 \leq i \leq T~), in ra ~k_i+1~ số nguyên dương: số thứ ~j~ (~0 \leq j \leq k_i~) là tổng của ~n_i~ số hạng đầu tiên của dãy số được cho bởi công thức ~u_t = t^j~. Vì đáp án có thể tương đối lớn, vậy nên PGP yêu cầu bạn in thẳng đáp án ra luôn, không ~mod~ gì cả.

Sample Input:

2
6 9
10 7

Sample Output:

6 21 91 441 2275 12201 67171 376761 2142595 12313161
10 55 385 3025 25333 220825 1978405 18080425

• Subtask 1: (10% số điểm): ~T \leq 10~ và ~n_i \leq 50~.
• Subtask 2: (20% số điểm): ~k_i \leq 6~.
• Subtask 3: (70% số điểm): Không có ràng buộc gì thêm.