[Solution] Square Counting solution codeforces

Square Counting solution codeforces – Luis has a sequence of 𝑛+1n+1 integers 𝑎1,𝑎2,,𝑎𝑛+1a1,a2,…,an+1. For each 𝑖=1,2,,𝑛+1i=1,2,…,n+1 it is guaranteed that 0𝑎𝑖<𝑛0≤ai<n, or 𝑎𝑖=𝑛2ai=n2. He has calculated the sum of all the elements of the sequence, and called this value 𝑠s.

Luis has lost his sequence, but he remembers the values of 𝑛n and 𝑠s. Can you find the number of elements in the sequence that are equal to 𝑛2n2?

We can show that the answer is unique under the given constraints.

Square Counting solution codeforces

Each test contains multiple test cases. The first line contains the number of test cases 𝑡t (1𝑡21041≤t≤2⋅104). Description of the test cases follows.

The only line of each test case contains two integers 𝑛n and 𝑠s (1𝑛<1061≤n<1060𝑠10180≤s≤1018). It is guaranteed that the value of 𝑠s is a valid sum for some sequence satisfying the above constraints.

Output

For each test case, print one integer — the number of elements in the sequence which are equal to 𝑛2n2.

Example
input

Copy
4
7 0
1 1
2 12
3 12

Square Counting solution codeforces

0
1
3
1
Note

In the first test case, we have 𝑠=0s=0 so all numbers are equal to 00 and there isn’t any number equal to 4949.

In the second test case, we have 𝑠=1s=1. There are two possible sequences: [0,1][0,1] or [1,0][1,0]. In both cases, the number 11 appears just once.

In the third test case, we have 𝑠=12s=12, which is the maximum possible value of 𝑠s for this case. Thus, the number 44 appears 33 times in the sequence.

 

Leave a Comment