ლარნაკები

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout


მოცემულია N ცალი ლარნაკი, რომელიც გადანომრილია 1-დან N-მდე. X ცალი ყვავილი ლარნაკებში ისე უნდა გაანაწილოთ, რომ სხვაობა ლარნაკების ნომრებსა და ყვავილების რაოდენობებს შორის ამ ლარნაკებში ტოლი უნდა იყოს ლარნაკთა ნებისმიერი წყვილისათვის. ამასთან, რაც შეიძლება ცოტა ყვავილი უნდა მოგვრჩეს. დაწერეთ პროგრამა, რომელიც გამოიტანს მორჩენილი ყვავილების რაოდენობას. თუ აღნიშნული წესით ჩალაგება ვერ ხერხდება, მაშინ ყველა ლარნაკი ცარიელი უნდა დარჩეს.

შესატანი მონაცემები: პირველ სტრიქონში ერთი მთელი რიცხვი T (1 <= T <=10^5) - ტესტების რაოდენობა, მომდევნო T სტრიქონიდან თითოეულში ორ-ორი მთელი რიცხვი - X (1 <= X <=10^18) და N (1 <= N <=10^9).

გამოსატანი მონაცემები: ერთი მთელი რიცხვი - მორჩენილი ყვავილების რაოდენობა.

 




მაგალითები

შესატანი მონაცემები
2 20 3 13 5 დაკოპირება
გამოსატანი მონაცემები
2 13 დაკოპირება