#P18057. Planting Trees

Planting Trees

Planting Trees

院子的左右两侧各有 dd 棵树。对于第 ii 对树,左侧第一天的原始高度为 xix_i,以后每天增长 fif_i;右侧对应的参数为 yi,giy_i,g_i。

每天观察前,分别反复剪去 mim_i 的高度,直到两棵树的高度都小于 mim_i。第一天也要进行修剪。

因此,在第 t+1t+1 天(t≥0t\ge0),两棵树的高度分别为

$$(x_i+t f_i)\bmod m_i,\qquad (y_i+t g_i)\bmod m_i.$$

对于每一对树,求前 nin_i 天中,左侧树严格矮于右侧树的天数。

输入格式

第一行一个整数 dd。接下来 dd 行,每行依次给出六个整数 fi,xi,gi,yi,ni,mif_i,x_i,g_i,y_i,n_i,m_i。

1≤d≤1041\le d\le10^4,上述六个参数均在 [1,106][1,10^6] 内。

输出格式

输出 dd 行,第 ii 行为第 ii 对树的答案。

样例

输入:

1
7 4 6 3 3 4

输出:

2