Al piccolo L piace piantare alberi.

Il piccolo L ha piantato $d$ alberi sia sul lato sinistro che sul lato destro del cortile. Sul lato sinistro, l'$i$-esimo albero ha un'altezza di $x_i$ metri il primo giorno e cresce di $f_i$ metri ogni giorno. Sul lato destro, l'$i$-esimo albero ha un'altezza di $y_i$ il primo giorno e cresce di $g_i$ metri ogni giorno.

Tuttavia, il piccolo L non vuole che gli alberi diventino troppo alti. Per mantenere tutto in ordine, per l'albero numerato $i$, se la sua altezza raggiunge o supera $m_i$, lo pota di $m_i$ metri finché la sua altezza non diventa inferiore a $m_i$.

Ora, il piccolo L vuole sapere, per l'albero numerato $i$, durante i primi $n_i$ giorni dopo la piantumazione, dopo aver effettuato la potatura ogni giorno, per quanti giorni l'albero di sinistra è più basso dell'albero di destra.

Nota: la potatura viene effettuata anche il primo giorno.

Input

C'è un solo caso di test in ogni file di test.

La prima riga contiene un intero positivo $d$ ($1 \le d \le 10^4$), che indica il numero di alberi su ciascun lato del cortile.

Ciascuna delle successive $d$ righe contiene sei interi positivi $f_i, x_i, g_i, y_i, n_i, m_i$ ($1 \le f_i, x_i, g_i, y_i, n_i, m_i \le 10^6$), con i significati descritti sopra.

Output

Stampa $d$ righe, ciascuna contenente un intero non negativo, che rappresenta il numero di giorni entro i $n_i$ giorni in cui l'albero di sinistra è più basso dell'albero di destra per l'albero numerato $i$.

Esempio

Input di esempio 1

1
7 4 6 3 3 4

Output di esempio 1

2

Note

Per il primo esempio, contiamo i primi $3$ giorni:

Giorno $1$: L'altezza iniziale dell'albero sul lato sinistro della strada è di $4$ metri, mentre l'albero sulla destra è di $3$ metri. L'albero di sinistra raggiunge il limite di $4$ metri, quindi viene potato. Dopo la potatura, l'albero di sinistra è di $0$ metri e l'albero di destra è di $3$ metri; quello di sinistra è più basso di quello di destra.

Giorno $2$: L'albero di sinistra è di $7$ metri e l'albero di destra è di $9$ metri. Entrambi superano i $4$ metri, quindi vengono potati. Dopo la potatura, l'albero di sinistra è di $3$ metri e l'albero di destra è di $1$ metro; quello di sinistra non è più basso di quello di destra.

Giorno $3$: L'albero di sinistra è di $10$ metri e l'albero di destra è di $7$ metri. Entrambi superano i $4$ metri, quindi vengono potati. Dopo la potatura, l'albero di sinistra è di $2$ metri e l'albero di destra è di $3$ metri; quello di sinistra è più basso di quello di destra.

Pertanto, l'output è $2$.