Con đường được gọi là bất tận, bởi vì ta không biết đâu là tận cùng của con đường. Cũng giống như những bóng đèn đường thắp sáng trên con đường bất tận, cũng là một dãy bất tận (được đánh số từ 1 trở đi), để mang ánh sáng đến toàn bộ con đường. Việc có thể thắp sáng và quản lý những bóng đèn là một vấn đề khó khăn. Chính vì vậy nên nhà phát minh Fata đã nghĩ ra một giải pháp. Anh tạo ra một bộ chip gồm 40 bit (từ 1 đến 40), mỗi bit có 2 trạng thái là bật và tắt, nếu bit thứ i được bật thì những bóng đèn có số hiệu là bội số của i sẽ được bật.

Theo cách mà Fata nghĩ ra, mỗi bóng đèn có thể được bật bởi một hoặc nhiều bit, và sẽ tắt nếu như không chịu ảnh hưởng bởi bit nào. Bây giờ, Fata muốn xác định, nếu như anh ta có chip X, thì bóng đèn thứ K được bật là bóng đèn nào? Vì Fata rất yêu thích số nguyên tố, nên trên con chip của anh ta, nếu một bit được bật thì bit đó phải có số thứ tự là một số nguyên tố (tức là bit 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)

Input:

• Dòng đầu tiên chứa số nguyên Q là số tests

• 2xQ dòng tiếp theo, mỗi cặp chứa 2 dòng mô tả một test:

  • Một dòng chứa dãy gồm 40 bit (0 hoặc 1) tương ứng là trạng thái (tắt hoặc bật) của từng bit trên con chip X

  • Dòng tiếp theo chứa số K

Output:

• gồm Q dòng, mỗi dòng ghi một số là số thứ tự của bóng đèn thứ K được bật tương ứng với mỗi test.

Sample Input

3
0110000000000000000000000000000000000000
5
0010000000000000000000000000000000000000
5
0100000000100000001000100000101000001000
16807

Sample Output

8
15
26866

Ràng buộc

Ràng buộc:
- Q ≤ 200 
- K ≤ 10^15