Max Distance

Ở đất nước X, chính phủ muốn chia N con bò ra thành K nhóm (mỗi nhóm có ít nhất 1 con bò) sao cho 2 con bò ở 2 nhóm khác nhau phải di chuyển 1 vài kilomet để gặp nhau. Bò x và Bò y (1 ≤ x < y ≤ N) sẽ phải di chuyển (2019201913x+2019201949y) mod 2019201997 kilomet để gặp nhau. 
Giả sử bạn đã chia được n con bò vào k nhóm (mỗi nhóm có ít nhất 1 con bò), gọi M là số kilomet ít nhất mà 2 con bò bất kỳ ở 2 nhóm khác nhau phải đi để gặp nhau. 
Bạn hãy tìm cách chia để M là lớn nhất.

Ví dụ:

• Với n = 3, k = 2 thì đáp án là 2019201769.
• Giải thích:
  • Bạn được cho 3 con bò và phải chia vào 2 nhóm sao cho mỗi nhóm đều có ít nhất 1 con bò.
  • Cách chia tối ưu là:
    • Nhóm 1: Bò số 1
    • Nhóm 2: Bò số 2 và 3.
    • Ta có: Bò 1, 3 phải di chuyển 2019201769 km để gặp nhau. Bò 1, 2 phải di chuyển 2019201817 km để gặp nhau. 
    • Đáp án là Mmax = min(2019201769, 2019201817) = 2019201769.
• Trong bài này bạn sẽ được cho T test, mỗi test có dạng ni,ki .

[Đầu vào/ Đầu ra]:

• [Giới hạn thời gian]: 0.5s với C++, 3s với Java & C#, 4s với Python,Go,Js.
• [Đầu vào]: 1 mảng T gồm |T| cặp số (ni,ki) (1 ≤ ni ≤ 7500) (2 ≤ ki ≤ ni) (1 ≤ |T| ≤ 105).
• [Đầu ra]: Gồm |T| số tương đương với đáp án của test thứ i.