9578: 彩票

你是一家彩票店的老板，每天都有许多顾客光顾你的店铺，其中有一位特别的顾客——小$A$。他是一个忠实的彩票爱好者，每天都会来店里购买一张彩票。 你的彩票游戏规则很简单： - 每张彩票允许顾客从$1$到$n$之间选择$k$个数字进行投注，且允许重复选取相同的数字。 - 每天晚上，会进行一次开奖，从$1$到$n$之间独立随机抽取$m$个数字，开奖数字可能会有重复。 - 然而，作为彩票店老板，你深知这个世界并不公平... 事实上，每一天的开奖都是被操控的——在第$i$天开奖时，数字$(i \mod n)+1$一定不会出现在开奖结果中！换句话说，每天的开奖数字实际是从去掉这一数字的$n-1$个数字中独立均匀随机抽取的。 小$A$并不知道这个秘密，他对选号十分懒惰，每天按照一套固定的方式选择他的投注号码，连续购买$T$天。在第$i$天，他选择的第$j$个数字是： $((i \cdot j + i + j) \mod n) + 1$，其中$i=1,2,...,T$（表示第$i$天），$j=1,2,...,k$（表示第$j$个选中的数字）。 每天小$A$的中奖金额可以用如下的公式来计算：对于每个$u=1,...,n$，设$c_u$是$u$出现在小$A$的当天投注数字中的次数，$d_u$是$u$出现在当天开奖数字中的次数，那么这一天小$A$的中奖金额则是$\sum_{u=1}^n c_u d_u$。 作为彩票店的老板，小$A$的奖金是由你来支付的。所以，你需要计算，一张彩票的售价至少应为多少，才能确保你从小$A$的这$T$天的投注中，获得非负的期望收益。注意，一张彩票的售价一定是一个整数。

输入包含一个整数$Q$（表示有$Q$组独立的测试数据），满足$1 \leq Q \leq 120$。接下来每组测试数据包含四个整数： $n$ $k$ $m$ $T$ - $n$（$2 \leq n \leq 10^6$）：可选的数字范围是$1,2,...,n$ - $k$（$1 \leq k \leq n$）：小$A$每天选择数字个数 - $m$（$1 \leq m \leq 10^5$）：每天开奖时抽取的数字个数 - $T$（$1 \leq T \leq 10^5$）：小$A$买彩票的天数 保证所有数据$T$的总和不超过$10^6$。

对于每组测试数据，输出一个整数，表示一张彩票的最低售价，以保证你的期望收益非负。

第$1$天，小$A$会投注数字$1$，而数字$1$和$3$可能中奖，因此小$A$获得的奖金的期望是$\frac{1}{2}$； 第$2$天，小$A$会投注数字$3$，而数字$1$和$2$可能中奖，因此小$A$获得的奖金的期望是$0$； 第$3$天，小$A$会投注数字$2$，而数字$2$和$3$可能中奖，因此小$A$获得的奖金的期望是$\frac{1}{2}$； 第$4$天，小$A$会投注数字$1$，而数字$1$和$3$可能中奖，因此小$A$获得的奖金的期望是$\frac{1}{2}$。 最终，小$A$获得总奖金的期望是$\frac{3}{2}$。因为小$A$要买$4$张彩票，因此一张彩票售价为$1$，就足以保证彩票店的期望收益非负。