Decorated Slots

Problem

A decorator is tiling a long hallway with N floor slots numbered 1 to N. Three tile patterns are available. Pattern a is placed on every slot whose number is a multiple of a. Pattern b is placed on every multiple of b, and pattern c on every multiple of c. A slot can receive more than one pattern, and it still counts as one decorated slot.

For each plan, count the decorated slots, meaning the slots that are a multiple of at least one of a, b, c.

Input

The first line has an integer T, the number of plans. Each of the next T lines has four integers N a b c.

Output

For each plan print the count on its own line.

Constraints

• 1 ≤ T ≤ 20000
• 1 ≤ N ≤ 10¹⁸
• 1 ≤ a, b, c ≤ 10⁹
• The least common multiple of the three numbers can be far larger than 64 bits.

Notes

In the first plan the decorated slots up to 10 are 2, 3, 4, 5, 6, 8, 9 and 10. Slot 6 is a multiple of both 2 and 3, and slot 10 is a multiple of both 2 and 5, but each slot counts once. That is 8 slots.