B. Divisor Query
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Lets see how well u know your divisors, you are given q queries of two types

  • Type 1: $$$1~l~r$$$ — Return number of values having odd number of divisors between $$$l$$$ and $$$r$$$
  • Type 2: $$$2~l~r$$$ — Return number of values having even number of divisors between $$$l$$$ and $$$r$$$
Input

The first line contains one integer $$$q$$$ ($$$1 \leq q \leq 10^6$$$) — the number of queries.

Then, the next $$$q$$$ lines contain the following types of queries:

  • Type 1: $$$1~l~r$$$ — ($$$1 \leq l, r \leq 10^9$$$)
  • Type 2: $$$2~l~r$$$ — ($$$1 \leq l, r \leq 10^9$$$)
Output

For each query of type 1, return the number of numbers having odd number of divisors, and for each of type 2, return the number of numbers having even number of divisors

Example
Input
20
1 97 183
1 57 71
1 57 91
2 14 93
2 23 81
1 73 154
2 79 143
1 82 110
2 67 132
1 23 63
1 83 145
2 14 18
1 73 132
1 34 67
1 48 82
1 96 193
2 3 19
2 62 151
2 66 134
1 76 119
Output
4
1
2
74
54
4
62
1
63
3
3
4
3
3
3
4
14
85
66
2