Masala #G8AL0DVWHL

Xotira 512 MB Vaqt 4000 ms
14

f(x)*f(x)*x

xx sonining chiroyliligi g(x)g(x) bilan belgilanadi. U quyidagicha hisoblanadi:

g(x)=f(x)f(x)xg(x) = f(x) * f(x) * x

Bu yerda f(x)f(x) - xxsonda ishlatilgan turli raqamlar soni. Masalan: f(1220)=3f(1220) = 3;f(93)=2f(93) = 2f(9876543210)=10f(9876543210) = 10. Sizga L,RL, R hamda MODMOD beriladi. Sizning vazifangiz [L,R][L, R] oralig'ida joylashgan barcha natural sonlarning chiroyliligini yig'indisini topish. Boshqa so'zlar bilan aytganda, quyidagini hisoblang:

x=lrg(x)\sum_{x=l}^{r} g(x)

Natija juda ham katta bo'lishi mumkin. Shu sabab javobning MODMOD ga bo'lgandagi qoldig'ini chop eting.


Kiruvchi ma'lumotlar:

Kirish faylida T(1T500)T (1 \le T \le 500) - testlar soni kiritiladi.

Keyingi TT ta qatorning har birida 3 ta natural sonlar - L,R(1LR10200)L, R (1 \le L \le R \le 10^{200}) va MOD(2MOD500)MOD(2 \leq MOD \leq 500)sonlari kiritiladi.

  • Subtask #1: T10T \le 10L=1L = 1R106R \le 10^6 (8 ball)
  • Subtask #2: T1T \le 1RL106R-L \le 10^6 (12 ball)
  • Subtask #3: T1T \le 1R1018R \le 10^{18} (20 ball)
  • Subtask #4: T2T \le 2R1050;MOD200R \le 10^{50}; MOD \leq 200 (30 ball)
  • Subtask #5: Hamma testlar uchun MOD=constMOD = const, ya'ni MODi=MODj (1i,jT)MOD_i = MOD_j \ (1 \le i, j \le T) (30 ball)

 


Chiquvchi ma'lumotlar:

Har bir test uchun alohida qatorda natijani chop eting.


Misollar
# input.txt output.txt
1
3
1 5 300
1 10 300
1 150 300
15
85
32
2
1
1234567790 1234567890 13
4
3
1
1234 123412341234 315
234
4
3
1 100 349
100 1000 349
1000 100000000000000000000 349
83
147
231
Izoh:

1-namunaviy test, 1-subtaskning 1-testiga to'g'ri keladi.

2-namunaviy test, 2-subtaskning 1-testiga to'g'ri keladi.

3-namunaviy test, 3-subtaskning 1-testiga to'g'ri keladi.

4-namunaviy test, 5-subtaskning 1-testiga to'g'ri keladi.