Rikka와 진분수

Rikka는 사랑스러운 소녀다. 예전에는 수학을 잘하지 못했지만, 남자친구 Yuta의 도움으로 크게 발전했다. 이제 Rikka는 혼자서도 수학 연구를 할 수 있게 되었다.

오늘 Rikka는 유리수 근사에 관한 자료를 읽고 있다. 분모가 $n$보다 작은 모든 분수 중에서 주어진 수 $x$에 가장 가까운 분수 $\frac{a}{b}$를 찾아 주는 연분수 전개 알고리즘에 Rikka는 흥미를 느꼈다.

Rikka는 이 문제의 난이도를 가늠해 보려고 한다. 그녀는 $x$보다 작은 분수 $\frac{a}{b}$와 $x$보다 큰 분수 $\frac{c}{d}$를 고른다. 그리고 구간 $[\frac{a}{b},\frac{c}{d}]$ 안에서 분모가 $n$ 이하인 분수로 나타낼 수 있는 유리수의 개수를 구하려고 한다. 형식적으로, $\frac{a}{b}$, $\frac{c}{d}$, $n$이 주어졌을 때 Rikka는 $\frac{a}{b} \leq \frac{e}{f} \leq \frac{c}{d}$를 만족하는 진분수 $\frac{e}{f}$ ($1 \leq e < f \leq n$, $\mathrm{gcd}(e, f) = 1$)의 개수를 구하려고 한다.

이 문제는 Rikka에게 너무 어려워 보인다. 그녀가 답을 구하도록 도와주자.

첫 번째 줄에는 테스트 케이스의 수 $t$ ($1 \leq t \leq 10^3$)가 주어진다.

각 테스트 케이스는 한 줄에 다섯 개의 정수 $n$, $a$, $b$, $c$, $d$가 주어진다 ($0 < \frac{a}{b} < \frac{c}{d} < 1$, $1 \leq a, b, c, d \leq 10^8$).

$\frac{a}{b}$와 $\frac{c}{d}$는 모두 진분수이고, $1 \leq n \leq 10^{10}$이며, $n > 10^6$인 테스트 케이스는 최대 $3$개임이 보장된다.

각 테스트 케이스마다 한 줄에 하나의 정수를 출력한다. 이는 답을 $998\,244\,353$으로 나눈 나머지이다.