Echoes of the Square#12468
Sign in

Echoes of the Square

2 seconds
256 megabytes
Medium

The sorcerers Kael and Liora have uncovered a final chamber containing stones with massive energy values. Liora notices that some stones possess an "Echoing Square" property.

A power stone with value is an Echoing Square if it satisfies all of the following conditions:

  1. is a perfect square.

  2. is not divisible by (i.e., its decimal representation does not end with the digit ).

  3. The decimal representation of is not a palindrome.

  4. The value V' obtained by reversing the digits of without leading zeros is also a perfect square.

Kael and Liora are given scrolls, each containing a range . For each scroll, they must determine how many Echoing Square stones exist strictly within that range (inclusive).

Input

The first line contains a single integer (1 \le Q \le 10^5) — the number of scrolls.

Each of the following lines contains two space-separated integers and (1 \le L \le R \le 10^{12}) — the bounds of the range specified on the scroll.

Output

For each scroll, output a single integer on a new line — the count of Echoing Square integers in the range .

Examples

Example 1

Loading
Loading

Note

In the first query, the range is . There are Echoing Squares:

  • (12^2 = 144, reversed is 441 = 21^2)

  • (13^2 = 169, reversed is 961 = 31^2)

Note that is a perfect square but is a palindrome, so it is excluded. is a perfect square but ends in , so it is excluded.

In the second query, the range is . The Echoing Squares are 144, 169, 441, and . Therefore, the answer is .

Scoring

  • Subtask 1 (75 points): 1 \le Q \le 1000 and 1 \le L \le R \le 10^5.

  • Subtask 2 (150 points): Original constraints.