There are $k$ piles of stones in a circle, labeled from $0$ to $(k -1)$, where the number of the stones in each pile is $n$ initially.
You can do some operations in rounds. The operation of the $i$-th round is to change the pile labeled $((i -1) bmod k)$, which allows you to remove some (at least one) stones from this pile, such that the old number of stones in this pile is a multiple of the new number. It also implies that you need to keep at least one stone in the pile after this operation.
The game will end if at least one pile contains only one stone. Given the positive integers $n$ and $k$, your task is to calculate for each pile, the number of different ways to do operations which can cause the game to end so that this pile is the last changed one.
The integer $n$ can be gigantic, so $n$ would be given using its prime factorization, in other words, assuming that $n = product_{i = 1}^m p_i^(e_i)$ for distinct prime numbers $p_1$, $p_2$, $\\dots$, $p_m$, $m$ and $(p_i, e_i)$ would be given instead of $n$.
The answer may be fairly large, so you should output the answer modulo $985661441$ instead.
The input contains multiple (about $200$) test cases.
For each test case, the first line contains two integers $m$, $k$ ($1 <= m, k <= 10$).
The $i$-th line of the next $m$ lines contains two integers $p_i$, $e_i$ ($2 <= p_i <= 10^9$, $e_i >= 1$). It is guaranteed that $p_1$, $p_2$, $\\dots$, $p_m$ are distinct prime numbers and $sum_{i = 1}^m e_i <= 10^5$ for each test case.
It is also guaranteed that no more than $5$ test cases satisfy that $sum_{i = 1}^m e_i >= 10^4$.
For each test case, output "_Case #x: y$""_0$ y$""_1$ $\\dots$ y$""_(k -1)$_" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y_i$ denotes the number of different ways modulo $985661441$ for the pile labeled $i$ in the corresponding case.
## Input
The input contains multiple (about $200$) test cases.For each test case, the first line contains two integers $m$, $k$ ($1 <= m, k <= 10$).The $i$-th line of the next $m$ lines contains two integers $p_i$, $e_i$ ($2 <= p_i <= 10^9$, $e_i >= 1$). It is guaranteed that $p_1$, $p_2$, $\\dots$, $p_m$ are distinct prime numbers and $sum_{i = 1}^m e_i <= 10^5$ for each test case.It is also guaranteed that no more than $5$ test cases satisfy that $sum_{i = 1}^m e_i >= 10^4$.
## Output
For each test case, output "_Case #x: y$""_0$ y$""_1$ $\\dots$ y$""_(k -1)$_" in one line (without quotes), where $x$ indicates the case number starting from $1$, and $y_i$ denotes the number of different ways modulo $985661441$ for the pile labeled $i$ in the corresponding case.
[samples]
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of people, with $ 2 \leq n \leq 10^4 $.
Let $ A = (a_1, a_2, \dots, a_{2n}) $ be a sequence of $ 2n $ positive integers representing slice sizes, where $ 1 \leq a_i \leq 10^9 $.
**Constraints**
Each person consumes exactly two slices.
Each slice is assigned to exactly one person.
**Objective**
Partition $ A $ into $ n $ disjoint pairs $ (a_i, a_j) $ such that the maximum difference between the sums of any two pairs is minimized.
Let $ S = \{ s_1, s_2, \dots, s_n \} $, where $ s_k = a_{i_k} + a_{j_k} $ is the total pizza consumed by person $ k $.
Compute:
$$
\min \left( \max_{1 \leq k \leq n} s_k - \min_{1 \leq k \leq n} s_k \right)
$$