[Variants] An interesting counting problem related to square product task B Statement Given q queries, you must find answer for each query. For each query, you are given an positive integer n,k (1≤k≤n≤1013). Count the number of arrays a[] of size k that satisfies: 1≤a1<a2<⋯<ak≤n ai×ai+1 is a perfect square ∀1≤i<n Since the result can be large, output it under modulo 977555333311111. Input Data: The first line contains a single integer λ is the number of this subtask. The second line contains a positive integer q. The next q lines, the pth query will contain 2 positive integers k,n. Output Data: In the p-th line, output a single number is the answer for query (np,kp) under modulo 977555333311111. Constraints: Subtask 1: 10.00% tests λ=1 for 1≤q≤100.000 queries of 1≤k≤log2(n)≤n≤10^11/q Subtask 2: 10.00% tests λ=2 for 1≤q≤100 queries of 1≤k≤n≤100. Subtask 3: 10.00% tests λ=3 for 1≤q≤10 queries of 1≤k≈√n≤n≤1010 Subtask 4: 10.00% tests λ=4 for 1≤q≤10 queries of 1≤k≈√n3≤n≤1010 Subtask 5: 10.00% tests λ=5 for 1≤q≤100 queries of 1≤k≤n≤222 and k,n are power of two. Subtask 6: 10.00% tests λ=6 for 1≤q≤1000 queries of 1≤k≈√n≤n≤107 Subtask 7: 10.00% tests λ=7 for 1≤q≤1000 queries of 1≤k≈√n3≤n≤107 Subtask 8: 10.00% tests λ=8 for 1≤q≤10.000 queries of 1≤k≈√n≤n≤104 Subtask 9: 10.00% tests λ=9 for 1≤q≤10.000 queries of 1≤k≈√n3≤n≤104 Subtask 10: 10.00% tests λ=10 for q=1 query of 1≤k≤n≤1013 Intended solution: O(√nloglog√n) per query. Input 1: 10 1 2 1 Output 1: 2 Explanation 1: There are 2 satisfied arrays {1}, {2}. Input 2: 2 3 10 2 25 2 27 3 Output 2: 4 16 12