One day Alice was experimenting with the numbers to make new algorithms. He introduce a…
- User
One day Alice was experimenting with the numbers to make new algorithms. He introduce a new term Rsum. Rsum of any number is defined as number obtained by iterative summing of digits of the given number until single digit number is obtained. For example: 365 --> (3+6+5) = 14 14 --> 1+4 = 5
Rsum(365)=5Naughty Bob came in the room of Alice in his absence and change all the numbers on which Alice was experimenting by their corresponding factorials. For example Bob will change 3 with 6 (3!=321). Consider 0!=0.
When Alice start experimenting without knowing that the numbers are now changed. He got some ambiguous results and unable to find some pattern for his algorithm. So he wants your help. You are given a range [A,B] of actual numbers and your task is to find sum of all Rsum values in range [A,B] of new changed numbers. Input: First line consist of T test cases. Next T line contain two integers a,b in each line.
Output: Find Sum of Rsum of all numbers in given range [A,B].
Constraints: 1 ≤ T ≤ 10^5 0 ≤ A ≤ B ≤ 10^6
SAMPLE INPUT 2 1 3 3 4
SAMPLE OUTPUT 9 12
Explanation
Test case 1: 1!=1 and Rsum(1)=1, 2!=2 and Rsum(2)=2, 3!=6 and Rsum(6)=6. So the sum of Rsums is 1+2+6=9.
Similarly for Test case 2.
Assistant
We are told: "Rsum of any number is defined as number obtained by iterative summing of digits of the given number until single digit number is obtained." That is essentially the digital root, except that for 0? digital root of 0 is 0. However note: factorial of 0 is given as 0 (since they say 0! = 0, but mathematically 0! = 1, but problem explicitly says "Consider 0! = 0." So for 0, we have factorial 0. Then Rsum(0) is iterative digit sum until single digit: 0 -> single digit 0. So Rsum(0) = 0.
We have T up to 1e5, A,B up to 1e6. For each query [A,B], we need sum of Rsum(n!) for n from A to B. Brute force would be precomputing n! up to 1e6? That's impossible because factorials huge. But we need only Rsum(n!) which is digital root of n!.
But digital root of a number is equal to n mod 9, except when n%9==0 then digital root is 9, unless n=0 then digital root 0. Actually digital root dr(n) = 1 + ((n-1) mod 9) for n>0, and dr(0)=0. Equivalent: dr(n) = n mod 9 if n%9 != 0, else 9 (if n>0). For n=0, dr(0)=0.
So we need dr(n!). So we need n! mod 9? But careful: digital root is computed from digit sum, but the above equivalence holds for any non-negative integer. So we can compute dr(n!) = (n! mod 9) unless n! mod 9 == 0 and n! !=0, then dr=9. But note: n! for n>=6 is divisible by 9 because 3^2 appears. Actually 6! = 720, divisible by 9? 720/9=80, so yes divisible by 9. So for n>=6, n! mod 9 = 0, so digital root would be 9 (unless n!=0? but n! >0). Wait, but there is nuance: digital root of a multiple of 9 is 9 (except number 0). So for n>=6, dr(n!)=9. Check: 6! =720, sum digits=7+2+0=9 => dr=9. 7! =5040, sum=5+0+4+0=9 =>9. 8! =40320 sum=4+0+3+2+0=9. 9! =362880 sum=3+6+2+8+8+0=27->9. So indeed for n>=5? Let's check n=5: 5!=120, sum=1+2+0=3, dr=3, not 9. 4!=24 ->6, 3!=6 ->6, 2!=2->2, 1!=1->1, 0!=0->0. So pattern: For n >= 6, dr(n!) = 9. But is that always true? Let's test n=6: yes 9. n=10: 10! = 3628800, sum digits = 3+6+2+8+8+0+0 = 27 ->9. So indeed because n! includes factors 3 and 6 (which contributes factor 3) and 9 etc. For n>=6, the exponent of 3 in prime factorization of n! is at least 2? Let's compute: exponent of 3 in n! is floor(n/3) + floor(n/9) + floor(n/27)+... For n=5: floor(5/3)=1 + floor(5/9)=0 => exponent=1, so only one factor 3, so not necessarily divisible by 9. For n=6: floor(6/3)=2 + floor(6/9)=0 => exponent=2, so divisible by 9. So yes, for n>=6, floor(n/3) >=2 => exponent >=2, so n! divisible by 9. So dr(n!)=9. However, there is a catch: digital root of a number that is divisible by 9 but not zero is 9. So indeed.
But wait: Is there any scenario where n! mod 9 = 0 but dr=9? Yes always. So we can compute dr(n!) as: If n == 0: 0 else if n <= 5: compute n! then dr manually. else: 9.
But hold on: is this always true for n>=6? Let's verify n=12: 12! has many factors, definitely divisible by 9. So dr=9. So answer for any n >=6 is 9.
Therefore the sum over [A,B] of dr(n!) = sum_{n=A}^{B} f(n), where f(n) = dr(n!). We can precompute f(n) for n from 0 to 5, and for n >= 6, f(n)=9.
But note: The problem says "Bob will change all the numbers ... by their corresponding factorials." So each original number n is replaced by n! (with 0! = 0). Then Alice computes Rsum of that new number. So our mapping is f(n)=Rsum(n!).
Thus, for each query [A,B], sum = (number of integers from max(A,6) to B)*9 + sum_{n=A}^{min(B,5)} f(n). But careful: if A <=5, include those.
Also we must consider n=0: f(0)=Rsum(0) = 0 (since 0! =0, iterative digit sum of 0 is 0). So include 0 if in range.
Now we can answer queries in O(1) after precomputing prefix sums of f(n) up to 1e6, but also we can compute on the fly using logic. Since T up to 1e5 and range up to 1e6, we can precompute an array f[0..1e6], with f[n]=dr(n!) as described, and then compute prefix sum array S[n] = sum_{i=0}^{n} f[i]. Then answer = S[B] - S[A-1] (with S[-1]=0). That is trivial.
But we need to compute f[n] for n up to 1e6? For n >=6, it's constant 9. So we can fill array quickly.
But careful: Is there any nuance about large factorials causing mod 9 calculation? Could n! mod 9 be 0 for all n>=6? Yes, because n! for n>=6 contains at least two factors of 3, so divisible by 9. But wait: what about n=6: yes, contains 3 and 6 => 36=18, includes 3^2? Actually 6=23, 3=3, so product has 3^2, so divisible by 9. So fine.
However, digital root is sum of digits repeated until single digit. For numbers that are multiples of 9 but not zero, digital root is 9. So f(n)=9 for n>=6.
But is there any exception if n! is 0? Only n=0 yields 0, which we treat separately.
So the solution is straightforward.
But wait: Check sample: Input: 1 3 => sum= f(1)+f(2)+f(3)=1+2+6? f(1)=1, f(2)=2, f(3)=6? Actually 3!=6, digital root of 6 is 6 (since 6 <10). So sum=9. Matches.
Test case 2: 3 4 => f(3)=6, f(4)=24->2+4=6, so sum=12. matches.
So far so good.
But what about n=5: f(5)=120->1+2+0=3. That's correct.
n=6: 720->7+2+0=9. So yes.
Thus answer for any range can be computed quickly.
Potential pitfalls: T up to 1e5, input reading speed needed. Use fast I/O.
Also A and B can be up to 1e6 inclusive. So we need array size 1e6+1.
We'll precompute f[0..5] manually, and for i=6 to 1e6 set f[i]=9. Then compute prefix sums.
Edge Cases: A=0, B=0 => answer f(0)=0. A=0, B=5 => sum of f(0..5) = 0+1+2+6+6+3? Let's compute: f0=0, f1=1, f2=2, f3=6, f4=6, f5=3 => total = 0+1+2+6+6+3=18. Indeed.
But careful: f(4)=? 4! =24, digital root: 2+4=6. f(4)=6. Good.
Now, one more nuance: The problem statement says "Rsum of any number is defined as number obtained by iterative summing of digits of the given number until single digit number is obtained." Typically for numbers that are multiples of 9, the iterative sum yields 9 (unless number is zero). So correct.
Thus solution is straightforward.
But hold on: Check n=6: 6!=720, digital root = 7+2+0=9, good.
n=9: 9! = 362880, sum digits = 27 -> 2+7=9, good.
Now, what about n=0: they explicitly say "Consider 0! = 0." So f(0) = dr(0) = 0.
Now, what about n=1? f(1)=1. n=2: 2!=2. n=3:6. n=4:24->6. n=5:120->3.
That seems all.
Thus we can answer.
But I want to double-check the constraint: A ≤ B ≤ 10^6. So we can precompute.
But is there any nuance: Could the factorial be too large? We're not computing it, we're only using properties.
But wait: The problem statement may have twist: "Rsum of any number is defined as number obtained by iterative summing of digits of the given number until single digit number is obtained." That's exactly digital root. So the approach is correct.
But also note: Sometimes digital root can be computed as 1 + (n-1) mod 9, for n>0. That would give for n! mod 9 =0, digital root 9. So fine.
Thus, the solution is trivial.
But maybe there is catch: For very large n (up to 10^6), n! is huge, but the property holds: It is divisible by 9 for n>=6. However, need to ensure that for n>=6, n! is not zero, which is true. So dr(n!)=9.
Thus answer queries quickly.
We should also consider possibility of A or B > 10^6? But constraints say B ≤ 10^6, so fine.
Now, implement.
Implementation steps:
- Define MAX = 1000000.
- Create array f of size MAX+1.
- Set f[0] = 0 (0! = 0, dr(0)=0).
- Compute factorial values for small n? But we can just compute dr for n=1..5 manually. f[1] = 1 (1! =1) f[2] = 2 (2! =2) f[3] = 6 (3! =6) f[4] = dr(24) = 2+4=6 f[5] = dr(120) = 1+2+0=3 For n=6 to MAX: f[n] = 9.
- Compute prefix sum array ps of size MAX+1, where ps[i] = sum_{k=0}^{i} f[k]. (use long long).
- For each test case, read A and B. Output ps[B] - (A>0? ps[A-1] : 0).
But careful: Input: first line T, then T lines each with two integers A and B. There may be multiple spaces, lines. Use scanf.
Edge: A may be 0, so we need ps[-1] defined as 0.
Complexities: O(MAX + T).
Now check sample: ps[0]=0 ps[1]=1 ps[2]=3 ps[3]=9 ps[4]=15 ps[5]=18 ps[6]=27 ... For query 1 3: ps[3]-ps[0]=9. Good. For query 3 4: ps[4]-ps[2]=15-3=12. Good.
Thus solution.
But wait: We should double-check f[5] = 3? 5! = 120 -> sum digits 1+2+0=3. Good.
Now, maybe there is nuance about digital root of 0! if it's 0. The problem says "Consider 0! = 0." So that's fine.
Thus answer done.
But is there any scenario where n! is so large that the digital root might be computed differently? No, property holds.
Thus we can provide code.
But wait: Could there be any tricky case where n>=6 but n! modulo 9 = 0 but digital root is 9? Yes.
Now, T up to 1e5, reading input quickly.
One more thing: Since we have MAX = 1e6, prefix sums array of long long 8 bytes, 8 million bytes, fine.
Now, also note: Input might have multiple testcases, need to output each answer on separate line.
We could also compute answer without prefix sum by counting numbers from A to B: If B<6, sum manually using small array; else compute counts. But prefix sum is easier.
Thus final solution.
But I suspect the problem might have been intended to be more complex, maybe the numbers are replaced by factorial and then Rsum of factorial, but perhaps they consider that factorial is huge and we cannot compute directly, but digital root property simplifies.
But careful: The digital root property holds for any integer, but we need to be cautious: For n>=6, n! is divisible by 9, but is it guaranteed that n! is not also divisible by some other number that might cause the digital root to be 9? Yes.
Thus solution.
Now, maybe there is a nuance: They defined Rsum as iterative sum of digits until single digit. That's exactly digital root, but note that for numbers that are multiples of 9, digital root is 9, except zero. So fine.
Thus code.
Now, we should also consider whether there is any need to compute n! mod something else? No.
Potential pitfalls: The input may have A > B? The problem says A ≤ B.
Now, let's write code.
Pseudo:
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1000000;
int main() { ios::sync_with_stdio(false); cin.tie(0);
vector<ll> f(MAXN+1); f[0] = 0; f[1] = 1; f[2] = 2; f[3] = 6; f[4] = 6; // 24 -> 2+4=6 f[5] = 3; // 120 -> 3 for (int i=6; i<=MAXN; i++) { f[i] = 9; } vector<ll> ps(MAXN+1); ps[0] = f[0]; for (int i=1; i<=MAXN; i++) { ps[i] = ps[i-1] + f[i]; } int T; cin >> T; while (T--) { int A, B; cin >> A >> B; ll ans = ps[B] - (A>0 ? ps[A-1] : 0); cout << ans << '\n'; } return 0;}
But need to ensure that we treat A, B as inclusive indices. Yes.
Now, confirm with sample.
We might also compute f[6] =9 etc.
One more nuance: The problem says "Bob will change all the numbers on which Alice was experimenting by their corresponding factorials." The numbers are originally maybe the numbers on which Alice was experimenting. Alice had numbers (maybe original numbers) but Bob changed each number to its factorial. So the numbers become factorials. Then Alice computes Rsum of each factorial. So yes.
Now, is there any chance that n! for n>=6 could be such that its digit sum is something else? For example, 6! = 720, digit sum 9. 7! = 5040, digit sum 9. 8! = 40320, digit sum 9. 9! = 362880, digit sum 27->9. 10! = 3628800, digit sum 27->9. So correct.
Thus the answer is simply counting numbers.
But wait, what about n=0? They defined 0! = 0. Rsum(0) = 0. Good.
Now, does any n! for n>=6 yield a digital root that is not 9? Possibly if the number is 0? But n! is never zero for n>=1. So okay.
Thus final.
But I'll also consider if they could have intended something else: Rsum defined as iterative sum until single digit. That's digital root. So fine.
Now, test with some custom values: A=0, B=0 => ans=0. Our code: ps[0]-ps[-1]? We'll handle A>0 condition, so ans = ps[0] - 0 = 0. Good.
A=0, B=1 => ans=1. Works.
A=5, B=6 => f[5]=3, f[6]=9 => sum=12. Our prefix: ps[6]=27, ps[4]=? ps[4]=15, wait ps[4]= f0..4: 0+1+2+6+6=15; then ps[6]=15+3+9=27? Actually ps[5] = 15+3=18, ps[6] = 18+9=27. So ans = ps[6]-ps[4] = 27-15=12. Good.
Now, we need to ensure that we set MAX = 1e6. That's fine.
But wait, the constraints: 1 ≤ T ≤ 10^5, and A,B ≤ 10^6. Our code runs O(T) queries and precomputation O(MAX). That's fine.
Now, one more nuance: The problem says "Sum of Rsum values in range [A,B] of new changed numbers." That is sum of Rsum of factorial of each n from A to B inclusive. So our mapping from n to f(n) is correct.
Now, could there be any misinterpretation: The numbers on which Alice was experimenting might be some arbitrary numbers, not necessarily the integers from A to B? But the problem says: "You are given a range [A,B] of actual numbers" meaning the original numbers are the integers in that range. So yes.
Thus final answer.
But wait: There's a nuance: They said "Bob change all the numbers ... by their corresponding factorials." So Bob replaces each number n with n!. So after change, the numbers are n! values. Then Alice, without knowing, computes Rsum on those numbers (the factorials). So we want sum of Rsum(n!) over n in [A,B]. So correct.
Thus solution is trivial.
But why would the problem be posed if the answer is just a simple pattern? Possibly because they expect the participants to figure out the pattern that for n>=6, Rsum is always 9. So it's a trick.
Now, confirm that for n=0, Rsum(0!)=Rsum(0)=0. For n=6 and above, always 9. So indeed.
Now, let's check n=6: f(6)=9. n=7=9, n=8=9, n=9=9, n=10=9, etc. So sum from A to B is 9*(count of n>=max(A,6) and ≤B) plus sum for n from A to min(B,5) with precomputed values.
Thus we can even answer without prefix array by simple count, but prefix array is simpler.
One more thought: Is there any scenario where n! could be 0? Only n=0 given that 0! =0 per problem statement. So fine.
Now, finalize.
But before finalizing, we should double-check small n factorial values and digital roots:
0! = 0 -> dr=0. 1! = 1 -> dr=1. 2! = 2 -> dr=2. 3! = 6 -> dr=6. 4! = 24 -> dr=2+4=6. 5! = 120 -> dr=1+2+0=3. 6! = 720 -> dr=7+2+0=9. 7! = 5040 -> 5+0+4+0=9. 8! = 40320 -> 4+0+3+2+0=9. 9! = 362880 -> 3+6+2+8+8+0=27 -> 2+7=9. 10! = 3628800 -> 3+6+2+8+8+0+0=27->9. All good.
Now, confirm the sum for range [0,10] using our method: sum = f0=0, f1=1, f2=2, f3=6, f4=6, f5=3, then f6..f10 each 9 -> that's 5 numbers? Actually 6,7,8,9,10 are five numbers? inclusive 6 to 10: count=5 => 9*5=45. Sum so far: 0+1+2+6+6+3=18, total=63. Let's compute quickly: 0!+... that sum of dr =? Might be 63. Not needed.
Now, verify using digital root property: n! mod 9 for n>=6 is 0, digital root =9. So correct.
Thus solution.
Now, potential issues: The problem might have constraints T up to 1e5, but also A and B up to 10^6. This solution is efficient.
One more nuance: Input format: "First line consist of T test cases. Next T line contain two integers a,b in each line." Sample shows two lines after T. So we need to read accordingly.
Now, code.
But careful: Because of the large T, we should use printf/scanf for speed, but using cin with ios_base sync turned off is fine.
Now, let's consider memory: f and ps arrays of size 1e6+1 as long long. That's about 8MB each? Actually long long 8 bytes * 1e6 = 8 million bytes = 8 MB. Two arrays => 16 MB, plus overhead, acceptable.
Alternatively we could compute answer on the fly without storing f for all indices, but easier to just store.
Now, final code.
But wait: Are we missing the possibility that the numbers could be negative? No, range from 0.
Thus final.
Now, before finalizing, I want to think if there's any other subtlety: The Rsum is defined as iterative sum until single digit. That's exactly digital root. However, there is a nuance: For numbers that are multiples of 9 but not 0, digital root is 9, but if the number is 0, digital root is 0. So correct.
Now, what about n=0? factorial defined as 0, so dr=0.
Now, test with A=0, B=0: output 0.
Now, let's also test with A=6, B=6: output 9.
Now, confirm the sample: good.
Thus answer.
Now, we can provide explanation.
But maybe there is nuance: The numbers are "actual numbers" and Bob changes them to factorial, but perhaps the range [A,B] is inclusive of those numbers? Yes.
Now, also note that the input can have multiple spaces, line breaks.
I'll produce code accordingly.
One more thing: The problem may have been originally in some contest where they expected precomputation of digital roots of factorials using some pattern. So it's fine.
But wait: Could there be any case where n! is zero? They define 0! = 0, but mathematically 0! = 1, but they explicitly say "Consider 0! = 0." So that's unique. So we must follow.
Now, double-check: For n=0, factorial =0, Rsum(0) = 0, because sum of digits of 0 is 0, which is a single digit. So output 0.
Now, I think the solution is correct.
But there might be a twist: The range [A,B] is of actual numbers, but Bob changes each number to its factorial, and then Alice calculates Rsum for each changed number. However, perhaps the range after changing is considered? But no, the problem says: "You are given a range [A,B] of actual numbers and your task is to find sum of all Rsum values in range [A,B] of new changed numbers." That is, sum over the original numbers in [A,B] of Rsum(factorial(original)). So we are correct.
Now, implementation details: We'll use C++.
But there is one more possibility: The range [A,B] is of the new changed numbers? That wording is ambiguous: "range [A,B] of actual numbers" so it's original numbers. Then "new changed numbers" refers to the numbers after Bob's modification. So sum over Rsum of those numbers. So it's correct.
Thus final.
Now, I'll produce the final answer.
But wait: The sample input: 2 1 3 3 4
Our code yields 9 and 12, matching.
Now, we can also compute f values for n>5 as 9. But careful: What about n=0? Already handled.
Thus code.
Now, I'll write final solution in Python? But given that T up to 1e5 and range up to 1e6, Python might be okay with precomputed list and prefix sums if using fast I/O. But typical online judges accept Python if optimized. However, since we are to provide solution reasoning, we can choose C++ for speed.
But the answer request is: we need to output the sum for each test case. So I'll provide C++ code.
Now, I'll produce final answer.
But also note: In some languages like Python, we need to handle big input. But here we are focusing on algorithm.
Now, final solution explanation:
- For n = 0, Rsum(0!) = 0.
- For n = 1 to 5, compute manually.
- For n >= 6, n! is divisible by 9, thus digital root is 9.
- Precompute prefix sums and answer queries.
Now, produce final answer.
But we should also verify for n=0, is 0! really defined as 0? Problem says "Consider 0! = 0." So we must use that.
Edge: For n=0, digital root of 0 is 0.
Now, check for n=0: Rsum(0) = 0. So sum includes 0.
Now, check if any query includes A=0, B large, our prefix includes f[0]=0, correct.
Now, final.
Now, I'll implement in C++.
One more note: I need to ensure that we use long long for sum to avoid overflow. Max sum: for B up to 1e6, each f(n) is at most 9, so sum <= 9e6, which fits in 32-bit int. But for many test cases it's okay to use long long anyway.
Now, code:
#include <bits/stdc++.h> using namespace std;
const int MAX = 1000000;
int main() { ios::sync_with_stdio(false); cin.tie(NULL);
vector<long long> f(MAX+1, 0); f[0] = 0; f[1] = 1; f[2] = 2; f[3] = 6; f[4] = 6; f[5] = 3; for (int i = 6; i <= MAX; ++i) { f[i] = 9; } vector<long long> pref(MAX+1); pref[0] = f[0]; for (int i = 1; i <= MAX; ++i) { pref[i] = pref[i-1] + f[i]; } int T; cin >> T; while (T--) { int A, B; cin >> A >> B; long long ans = pref[B] - (A > 0 ? pref[A-1] : 0); cout << ans << '\n'; } return 0;}
That should work.
Now, I'll also consider if we can compute answer on the fly to save memory: Since f is constant after 6, we can precompute a small array for 0..5. Then answer: if B < 6: sum using precomputed small array; else if A <=5: sum for A..5 using small array + 9 * (max(0, B - max(6, A) + 1)). But prefix array is easier.
Given that memory is okay, prefix is fine.
Now, test with some edge: A=6, B=1000000: ans = 9*(1000000-6+1) = 9999995 = 8,999,955? Let's compute using prefix: pref[1000000] = pref[5] + 9(1000000-5). pref[5]=18, 9*999995 = 8,999,955, total = 8,999,973? Actually 18+8,999,955 = 8,999,973. That is within int range? 8,999,973 < 1e7, fine. But for many queries, answer is within int, but we use long long.
Now, final answer.
But hold on: There is one more nuance: The digital root of a number that is multiple of 9 is 9 only if the number is non-zero. For n>=6, n! is non-zero, so ok.
Now, confirm that n! for n=0 is 0, so dr=0.
Thus final.
Now, I'll produce final answer with explanation.
But wait: The problem says "0! = 0". This is unusual, but we follow.
Now, also consider that maybe they consider 0! = 1 but then Rsum(1)=1. But they explicitly say "Consider 0!=0." So we follow.
Now, could there be any case where n! is so large that we might need to compute its digital root using some other property? No.
Thus final.
Now, I'll output solution.
But I'd like to consider if there is any potential off-by-one: For n=6, we set f[6]=9. That's correct.
Now, finalize.
Given the problem constraints, this solution is optimal.
Now, produce final answer. ```cpp
#include <bits/stdc++.h> using namespace std;
const int MAX = 1000000;
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
// precompute Rsum(n!) for all n up to 1e6 vector<long long> f(MAX + 1); f[0] = 0; // 0! = 0 -> Rsum = 0 f[1] = 1; // 1! = 1 -> Rsum = 1 f[2] = 2; // 2! = 2 -> Rsum = 2 f[3] = 6; // 3! = 6 -> Rsum = 6 f[4] = 6; // 4! = 24 -> 2+4 = 6 f[5] = 3; // 5! = 120 -> 1+2+0 = 3 for (int i = 6; i <= MAX; ++i) f[i] = 9; // for n >= 6, n! divisible by 9 -> digital root = 9 // prefix sums vector<long long> pref(MAX + 1); pref[0] = f[0]; for (int i = 1; i <= MAX; ++i) pref[i] = pref[i - 1] + f[i]; int T; cin >> T; while (T--) { int A, B; cin >> A >> B; long long ans = pref[B] - (A > 0 ? pref[A - 1] : 0); cout << ans << '\n'; } return 0;}