Kaosar and EM ( > w < )#12365

Kaosar and EM ( > w < )

2 seconds

256 megabytes

Medium

You are given $3$ integers $l$ , $r$ and $p$ you have to say how many integer $x$ are there in range $[l, r]$ [l,r]

such that

x \equiv ⌊ x ⌋ mod p

x\equiv \lfloor \sqrt x \rfloor \mod p

use sqrt decomposition ds

Input

The first line contains a single integer $t$ $(1 \leq t \leq 1 0^{3})$ (1\le t\le 10^3) the total number of test cases.

Each test case contains $3$ integers $l$ , $r$ $(0 \leq l \leq r \leq 1 0^{9})$ (0\le l\le r\le 10^9) and $p$ $(1 \leq p \leq 1 0^{5})$ (1\le p\le 10^5).

Output

Print the total number of $x$ in the range $[l, r]$ [l,r].

Examples

Example 1

Loading

Note

In first test case $1, 5, 8, 9$ 1,5,8,9 satisfy the condition so the answer is $4$ .

Scoring

Subtask $1$ ( $10$ points) : $(p = 1)$ (p=1)
Subtask $2$ ( $30$ points) : $r \leq 1 0^{3}$ r\le 10^3
Subtask $3$ ( $60$ points) : $\sum r - l \leq 1 0^{6}$ \sum r-l \le 10^6
Subtask $4$ ( $100$ points) : No additional constraints.

[l, r]

x \equiv ⌊ x ⌋ mod p

(1 \leq t \leq 1 0^{3})

(0 \leq l \leq r \leq 1 0^{9})

(1 \leq p \leq 1 0^{5})

[l, r]

1, 5, 8, 9

(p = 1)

r \leq 1 0^{3}

\sum r - l \leq 1 0^{6}