New Divisor Problem

rajon_aust Replay of Intra AUST Prog...
Limits 2s, 512 MB

In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case one says also that n is a multiple of m. An integer n is divisible by another integer m if m is a divisor of n; this implies dividing n by m leaves no remainder.

The problem is based on positive divisor. Give you n numbers (A1, A2, A3,…., An) and q query . Each query gives you three integers L, R, D. You have to print the number of distinct integers from L to R (inclusive) those have exactly D positive divisors.

Input

At first gives you an integer T (1 ≤ T ≤ 5), the number of test cases. For each test case:

The first line contains the integer n (n ≤ 100000).

In the second line, n positive numbers follow (the numbers will be less than or equal to 106).

The third line contains the integer q (q ≤ 100000).

Then q lines follow, where each line contains 3 numbers L, R (1 ≤ L,R ≤ n), and D (1 ≤ D ≤ 106).

Output

For every test case, print case number and require result.

Sample

InputOutput
2
5
2 3 2 7 17
2
1 5 2
2 5 2
4
2 12 3 12
2
1 4 6
1 4 2
Case 1:
4
4
Case 2:
1
2

For test case 2, there are 4 numbers: 2, 12, 3, 12.

2 has only 2 positive divisors: 1 and 2. 12 has 6 positive divisors: 1, 2, 3, 4, 6, and 12. 3 has only 2 positive divisors: 1 and 2. 12 has 6 positive divisors: 1, 2, 3, 4, 6, and 12.

For the first query, there are 2 integers from 1 to 4 those have exactly 6 positive divisors. These two numbers are 12 and 12. But considering only distinct numbers, you need to count 12 once. Therefore the answer is 1.

For the second query, there are 2 integers from 1 to 4 those have exactly 2 positive divisors. These two numbers are 2 and 3. That’s why the answer is 2.


Submit

Login to submit.

Contributors

Statistics

68% Solution Ratio
IamHotEarliest, Jan '18
kuriyama_miraiFastest, 0.1s
ShadowMeLightest, 8.7 MB
riyad000Shortest, 1334B
Toph uses cookies. By continuing you agree to our Cookie Policy.