题意

给定 $n,a,b,c,d$。

有长度为 $n$ 的序列 $A,B$ 满足 $A_{i}=a^i\bmod c,B_{i}=b^i\bmod d$。

求：$\sum_{i=1}^n[A_i=B_i]$。

输入格式

第一行输入一个整数 $T$，代表数据组数。

对于每组数据：一行五个正整数，依次为 $n,a,b,c,d$，含义如题面所述。

输出格式

输出 $T$ 行，每行一个整数，表示每组数据的答案。

样例 #1

样例输入 #1

2
10 2 3 7 11
20 2 3 7 11

样例输出 #1

0
2

数据范围与提示

特殊性质 $A:$ $\mathrm{lcm}(c-1,d-1)\leq10^7$。

特殊性质 $B:$ $n\bmod\mathrm{lcm}(c-1,d-1)=0$。

对于所有数据，满足 $1 \leq T \leq5,1\leq n,a,b \leq 10^{18},1\leq c,d \leq 10^7$。

保证 $c,d$ 均为质数。