Spam Tin Nhắn

Submit solution
Points: 3
Time limit: 1.0s
Memory limit: 488M
Author:
shioiori
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Hầu hết mọi người ai cũng dùng mạng xã hội như facebook, zalo... để nhắn tin cho nhau, trong đó có Milluki. Do rất stress vì đống figure bị đập, anh ta quyết định thư giãn bằng cách spam tin nhắn. Đúng hơn là, anh ta muốn spam một tam giác emote có kích thước \(k\) được tạo nên từ các dòng tin nhắn chứa ký tự đặc biệt. Nó bao gồm \(2k - 1\) tin nhắn, trong đó tin nhắn đầu tiên chứa 1 ký tự, tin nhắn thứ 2 chứa 2 ký tự,... tin nhắn thứ k chứa k ký tự, tin nhắn k+1 chứa k-1 ký tự, tin nhắn k+2 chứa k-2 ký tự,... và tin nhắn cuối cùng chứa 1 ký tự. Với kích thước k = 3, một tam giác emote có hình dạng như sau:

@

@@

@@@

@@

@

Tất nhiên, phần lớn các mạng đều bật kiểm duyệt việc spam. Chế độ kiểm duyệt sẽ đánh dấu bạn là spam tin nhắn khi bạn spam ít nhất \(x\) ký tự đặc biệt liên tiếp. Milluki tò mò rằng nếu anh ta cứ spam như vậy thì anh ta sẽ viết được bao nhiêu tin nhắn trước khi bị cấm, hay anh ta có thể viết hết tam giác emote?

Input

  • Dòng đầu tiên là số test case \(t\) (1 <= \(t\) <= 10^4)
  • Tiếp theo là \(k\) - kích thước của tam giác emoji và \(x\) - số ký tự đặc biệt ít nhất để bị đánh dấu là spam (1 <= \(k\) <= 10^9, 1 <= \(x\) <= 10^18)

Output

  • In ra số lượng tin nhắn viết được trước khi bị ban.

Example

Input 1

5
2 1
2 2
2 3
2 4
2 5

Output 1

1
2
2
3
3

Comments