题目描述

定义 $f(x)$ 表示将 $x$ 的翻转后的数，例如：$f(123)=321$。特别的，如果 $x$ 的末尾有 $0$，则忽略翻转后的前导 $0$，例如：$f(120300)=3021$。

小 D 会给你五个整数 $l,r,a,b,c$，请你求有多少个正整数 $x\in [l,r]$，使得 $x^a\bmod b=f(f(x)+c)$。

输入格式

本题单个测试点内有多组测试数据。

第一行一个正整数 $T$ 表示数据组数。

接下来 $T$ 行，每行五个整数 $l,r,a,b,c$，表示一组测试数据。

输出格式

一行一个整数，表示答案。

3
5 100 2 45 6
1 100 5 97 9
589 100425 1032 4855 4091

2
1
4

3
563 9980225344 100 23184 822
794 9982136054 19842 98213 603
1 10000000000 172455 199240 5061

20
11
39

提示

【样例解释】

对于样例 #1 的第一组测试数据，有两个正整数满足要求，分别是 $43,48$。

对于样例 #1 的第二组测试数据，有且仅有 $1$ 个正整数满足要求，为 $1$。

【数据范围】

对于所有数据，保证：

• $1\le T\le 3$。
• $1\le l\le r\le 10^{10}$。
• $0\le a,c\le 2\times 10^5$。
• $1 \le b \le 2 \times 10^5$。